- Should the first course introduce some of the fundamental algorithms of Sorting and Searching without introducing the notions of time and space complexity?
You should not, it would quite much obscure what the point of having different sorting algorithms is.
But you know, they surely could accept that they get an approximate figure (Big-O notation - it'll be enough to have an ordered table for the complexity classes in Big-O as reference) for the "best" and "worst" case of the algorithms now. The actual methodology for doing the complexity analysis could be delivered later.
This will not be a problem as long as your students don't have to learn these values by heart for the test(s), but get / can use reference sheets.
- A second course on designing algorithms. This course would cover not only time and space complexities but also generic algorithm design techniques such as Divide and Conquer, Dynamic Programming etc..
I'm not sure doing this while they are not yet familiar with C or any other programming language is clever. In effect, a little of this probably should be taught in the C course, the rest only after they have basic skills with at least one language and the programming tools they use to program it (including especially the debugger(s)).
Most of the text books I have considered are either too voluminous or too intimidating for the student with over emphasis on the analysis of the complexity of algorithms.
I think students get a bit upset about buying expensive books for one semester only for cost reasons, or lecturers expecting them to learn too much, or it being unclear what degree of knowledge actually is required in tests. If you take care to avoid this, a big book is fine, even desirable.
I wouldn't shy away from recommending (or maybe requiring) something like "Introduction to Algorithms" by Cormen et al. (and similarly large works for maths and so on) as teaching and reference material.
As a general doctrine, it is just really a good idea to pretend you're coaching students more or less specifically to pass a specific, not terribly low or high standards test you have in mind.
You're simply trying to offer time-efficient learning to that end. If a diagram doesn't seem good, do another better one, if some section in a book doesn't seem straight-forward or coherent or goes too far off the scope of the course, do your own. But you probably still require a good, detailed book as catch-all and provider of good text, because you aren't quite perfect.