CS 121

From CS Wiki
Jump to: navigation, search

CS 121: Computer Science II

Catalog Description: Introduction to abstract data types and fundamental data structures: linked lists, stacks, queues, trees, and graphs. Methods for implementing and algorithms for manipulation of these structures. Dynamic memory methods, sequential file processing, additional searching and sorting algorithms that result from using these data types, recursion, object-oriented programming. Three lectures a week.

Type: Required for all Computer Science majors

Total Credits: 3

Contact Hours: 3 lecture hours

Course Coordinator: Bruce Bolden

URL: http://www2.cs.uidaho.edu/~bruceb/cs121/

Prereq: CS 120 with a grade of "C" or higher.

Coreq: Math 176

Textbook: Kruse and Ryba, Data Structures and Program Design in C++, Prentice-Hall 1999 or equivalent text.

Textbook URL: http://www.pearsonhighered.com/educator/product/Data-Structures-and-Program-Design-in-C/9780137689958.page

Prerequisites by Topic:

  1. Combinations and permutations (Math 176)
  2. Proof by induction (Math 176)
  3. Working knowledge of C++ syntax and ability to develop programs from written descriptions (CS 120)
  4. Loops (CS 120)
  5. Arrays (1 and 2 D) and linked lists (CS 120)
  6. Recursion (CS 120)
  7. Basic object oriented programming concepts (CS 120)

Major Topics Covered

  1. Algorithms, programs and data structures (3 hours)
  2. Pointers, with arrays, dynamic memory (2 hours)
  3. Program complexity concepts (2 hours)
  4. Linked Lists (4 hours)
  5. Classes / Templates (2 hours)
  6. Stacks (1 hours)
  7. Queues (2 hours)
  8. Recursion (2 hours)
  9. Trees (5 hours)
  10. AVL Trees (2 hours)
  11. Other Trees (2-3, Red-Black, B-trees, etc.) (1 hour)
  12. Hashing (3 hours)
  13. Tables, priority queues, heaps (3 hours)
  14. Graphs (4 hours)
  15. Searching performance comparison (2 hours)
  16. Sorting techniques (insertion, merge-sort, and quick-sort) (3 hours)

Course Outcomes

Note: the primary Student Outcomes addressed in this course are (b), (f), (j) and (k). All are introduced.

  1. Make a description of a problem that has a straight forward computing solution, design, construct, and test a complete program that solves the problem. (c)
  2. Work in a small group to solve a relatively simple computing problem. (d)
  3. Understand the potential consequences of program failure. (e)
  4. Understand the expectations for academic integrity as they apply to software development. (e)
  5. Students will be able to document computer solutions with well written reports in a standard format that emphasizes insight into the problem solving, not just the presentation of the output. (f)
  6. Use a C++ compiler. (i)
  7. Use basic system tools (e.g., top and time) to analyze a program's behavior with respect to the use of computer memory and CPU time. (i)
  8. Use code libraries. (i)
  9. Define C++ constants and variables of type char, int, float, and double. They will know the different characteristics of these data types and when each type should be used. (j)
  10. Understand how to use type casting and how the compiler converts between types in mathematical/logical expressions. (j)
  11. Create correctly formatted C++ expressions using the following operators: +, -, #, %, ( ), and []. (j)
  12. Build program units consisting of the sequence, selection, and repetition programming structures of C++. More specifically they will be able to determine under what conditions each of the following structures should be used: Sequence: assignment statement; Selection: if, if-else, if-else if-else if-else, and switch structures; Repetition: for , while, and do-while structures. (j)
  13. Read/Write information to/from files. (j)
  14. Create and call functions having arguments and return values. They will know when arguments should be passed by value or reference. (j)
  15. Use and manipulate one and two dimensional arrays. (j)
  16. Use and understand the use of recursion. (j)
  17. Understand how to allocate memory dynamically using arrays and pointers. (j)
  18. Use and manipulate singly-linked lists using pointers. (j)
  19. Create simple classes having data members and member functions. They will be able to read class header files and be able to call object member functions defined in the header files. (j)