CS 121 Computer Science II

Total Credits: 4 cr

Course Coordinator: Terry Soule

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

Current Catalog Description: Introduction to abstract data types and fundamental data structures: linked list, stacks, queues, trees, and graphs. Methods for implementing and algorithms for manipulation of these structures. Dynamics memory methods, sequential file processing, additional searching and sorting algorithms that result from using these data types, recursion, object-oriented programming. Three sessions a week; and one 2-hour lab a week. Prereq: CS 120. Coreq:  Math 176.

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

References: None.

Course Goals: After taking this course a student should be able to solve problems that rely on the use of basic data structures (other than built-in) using C++. The student will be able to choose from several alternative implementations to optimize efficiency of the problem solution. Additionally, program design and development processes learned in CS 120 will be reinforced through the assignment of programming projects. Enhance the problem solving skills associated with programming, including top-down design, problem decomposition, algorithm analysis, program design and testing.

Prerequisites by Topic:

• Combinations and permutations (Math 176)
• Proof by induction (Math 176)
• Working knowledge of C++ syntax and ability to develop programs from written descriptions (CS 120)
• Loops (CS 120)
• Arrays and linked lists (CS 120)
• Recursion (CS 120)
• Basic object oriented programming concepts (CS 120)

Major Topics Covered in the Course: : (duration) (CC 2001 BOK reference)

• Algorithms, programs and data structures (3 hours) (PF2, AL2)
• Pointers, with arrays, dynamic memory (2 hours) (PF3)
• Program complexity concepts (2 hours) (AL1)
• Linked Lists (4 hours) (PF3)
• Classes / Templates (2 hours) (PL6)
• Stacks (1 hours) (PF3)
• Queues (2 hours) (PF3)
• Recursion (2 hours) (PF4)
• Trees (5 hours) (PF3, DS5)
• AVL Trees (2 hours) (PF3, DS5)
• Other Trees (2-3, Red-Black, B-trees, etc.) (1 hour) (PF3, DS5, AL3)
• Hashing (3 hours) (AL3)
• Tables, priority queues, heaps (3 hours) (AL3)
• Graphs (4 hours) (PF3, DS5, AL3)
• Searching performance comparison (2 hours) (AL1)
• Sorting techniques (insertion, merge-sort, and quick-sort) (3 hours) (PF3)

Laboratory projects (specify number of weeks on each): None.

• Introduction to Unix, use of editor and compiler to create a simple program (1 week)
• Manipulation of dynamically allocated 2-D Arrays (1 week)
• Linked list manipulation- Josephus problem (2 weeks)
• Long integers using liked list objects (2 weeks)
• Store simulation using queues (2 weeks)
• Movie /Actor lookup using binary search trees (2 weeks)
• Symbol table lookup using hash tables (2 weeks)
• Sorting / Searching (1 week)

Estimated Curriculum Category Content:

Area	Core	Advanced	Area	Core	Advanced
Algorithms	1 cr		Data Structures	1 cr
Software Design	1 cr		Prog. Languages	1 cr
Computer Arch			Other

Oral and Written Communications: The students in the course are not required to submit written reports.

Social and Ethical Issues: None.

Theoretical Content:

• Discuss code complexity of different solutions, e.g., iteration vs. recursion. (2 hours)

Problem Analysis:

• Algorithm analysis: Review O(N) concept, compare iteration and recursion using different structures (arrays, lists, and trees) (2 hours)
• Program testing: analyzing a problem (bug) and determining the state of variables during execution. (2 hours)

Solution Design: None.

• Top-down, decompositional design (2 hours)
• Bottom-up design (1 hours)

Course Outcomes: The following list documents the course outcomes and crossreferences them to the BSCS program outcomes. The letter at the beginning of each reference identifies the program outcome supported. The numbers sequentially identify the course outcome for this course. After completing CS 121 a student should be able to:

• Develop computer code using a modern high level programming language to solve a specific problem. (a-1)
• Understand and apply concepts of computer science as required during the solution of a computing problem. (a-2)
• Understand and apply appropriate scientific methods and principles to investigate the behavior of a program or programming language. (a-3)
• Design a program based on project requirements. (c-1)
• Write a program based on their design and the project requirements. (c-2)
• Write C++ classes, including: (c-3)
  a. constructors
  b. destructors
  c. public and private data and methods
  
• Write code to generate, use, and maintain complex dynamic structures, including: (c-4)
  a. linked lists
  b. stacks
  c. queues
  d. tables
  e. trees
  
• Write code using standard algorithms, including, but not limited to: (c-5)
  a. recursion
  b. bubble and quick sort
  c. hashing d. binary searches
  e. tree balancing
  
• Work in a small group to solve a relatively simple computing problem. (d-1)
• Adequately comment a program written in a high level language. (f-1)
• Learn to use newly introduced code libraries. (h-1)
• Use a C++ compiler. (i-1)
• 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-2)
• Use code libraries. (i-3)
• Write proficiently in C and C++. (j-1)