22C:21 Computer Science II: Data Structures
10:30-11:20 MWF, Room 109 EPB
Sriram V. Pemmaraju
101G MLH, firstname.lastname@example.org, 319-353-2956
Office Hours: 11:30 to 12:30 on MW, 9:30 to 10:30 on F
This is the second in the sequence of core undergraduate computer science
courses and is required for all computer science majors and minors.
It builds on the first courses, Computer Science I: Fundamentals (22C:16) and
and is concerned mainly with the design and implementation of data structures,
algorithms for accessing and manipulating data structures,
and the application and uses of data structures.
Java is the programming language of choice for this course.
Information about TAs,
Quizzes, Projects, and Exams,
There are three TAs for the course: Alankar Kampoowale, Yan Wang, and Zhihong Wang.
They will lead one discussion section each.
Section Time Location TA
A01 12:30-1:20 Tuesday C29, PC Alankar Kampoowale
A02 2:30-3:20 Thursday 71 SH Zhihong Wang
A04 3:30-4:20 Thursday 210 MLH Yan Wang
Contact information and office hours for the TAs is as follows.
Name Office Phone e-mail Office hours
Alankar Kampoowale B20J 335 3650 email@example.com 12-1, MW
Zhihong Wang 301 MLH TBA firstname.lastname@example.org 2-3, WF
Yan Wang B20J 335 3650 email@example.com 1:30-2:30 T, 2:30-3:30 Th
- There will be no meetings of the discussion sections in the first week of classes (8/22-8/26).
- Reading for week 1, 8/22-8/26: Chapter 1, Chapter 2 (62-72).
- Discussion section topic, week 2, 8/29-9/2: Overview of 1-dimensional arrays, resizing arrays
- Reading for week 2, 8/29-9/2: all of Chapter 2.
- Discussion section topic, week 3, 9/5-9/9: Multi-dimensional arrays
- Homework 1 posted; due on 9/7 in class.
- Reading for week 3, 9/5-9/9: Chapter 6 (on recursion).
- Solution to Homework 1 posted.
- Discussion section topic, week 4, 9/12-9/16: The Vector class from the Java collections
- Reading for week 4, 9/12-9/16: Merge Sort (pp 279-294, Chapter 6) and Quick Sort (pp 325-357,
- Homework 2 posted; due on 9/23 in class.
- Project 1 posted; due at midnight 10/17.
- Reading for week 5, 9/19-9/23: Quick Sort (pp 325-357) and
Graphs (Chapter 13, pages 615-623).
- Reading for week 6, 9/26-9/30: Graphs (Chapter 13, pages 615-623) and
depth first graph traversal (pages 623-636).
- Midterm (open notes/book) on 10/14, Friday, in class. Here
are more details.
- Solution to Homework 2 posted.
- Suggestions/Clarifications for Project 1.
- Homework 3 posted; due on 10/14 in class.
- How to electronically submit your project.
You will need to do this from a CS department machine.
- This week (10/10-10/14) the TAs will do a
midterm exam review in the discussion sections.
- There is no class on Monday, 10/17. Project 1 is due by midnight
on Monday, 10/17.
- Solution to Homework 3 posted.
- Solution to the midterm exam posted.
- Solution to the Project 1 posted. Feel
free to use this code in Project 2.
- Project 2: Part I posted. Due back on 10/31, midnight.
Part II will be posted this week.
- This week (10/24-10/28) the TAs will discuss doubly linked
lists in the discussion sections.
- Older compilers are having trouble compiling myGraph.java
because it uses generics. Here is a version of myGraph.java that does not use generics and should compile
fine on older compilers as well. It is the same as myGraph.java
except for two lines of code in the depth first traversal function.
- The submission folder for project2.1 is now ready. Project2.1 is due
on Monday, 10/31, by midnight.
- Grades so far. Please report any
errors you find.
- Project 2: Part II posted. Due back on 11/7, midnight.
Part III will be posted this week.
- Concerning Project 2.1: there is no way to implement the
getNeighbors function in the myGraph class without making
further modifications to the LinkList class. What I said in class
on Monday (10/31) is incorrect. Please submit the modified LinkList
class as well. Due to the confusion caused by this, the deadline for
Project 2.1 is extended to Tuesday, 11/1, midnight.
- Clarifications for Project 2.2.
- Project 2.2 submission directory is now open.
- Project1 grades. If you want an explanation, please contact our TA, Yan Wang.
- Project 2.1 is due at midnight on Tuesday, 11/8.
- Project 2: Part III is posted. Due back on 11/15, midnight.
- Clarifications for Project 2.3.
- Homework 4 is posted. Due on 11/28.
- Project 3 is posted. Due on 12/14.
- Final exam details. Final exam is on Thursday, Dec 15th,
7:30am-9:30am, in 107 EPB.
- Week 1 (8/22-8/26): Run-time analysis and the "Big Oh" notation. Wednesday 8/24 and
- Week 2 (8/29-9/2): Slow sorting algorithms (bubble sort) and recursion.
Wednesday 8/31, and
- Week 3 (9/5-9/9): Recursion and faster sorting algorithms (merge sort).
Wednesday 9/7, material covered on Friday, 9/9 appears
in the textbook, pages 279-294.
- Week 4 (9/12-9/16): Divide and conquer, merge sort (continued), and quick sort,
material covered this week appears in the textbook, pages 325-357.
- Week 5 (9/19-9/23): Improving the running time of quick sort (median-of-3 rule, randomization), graphs, adjacency matrix representation.
- Week 6 (9/26-9/30): The myGraph class, primitive operations
such as addVertex, addEdge, deleteVertex,
deleteEdge, and getNeighbors.
- Week 7 (10/3-10/7): Graph traversal, depth-first traversal using
the Stack data structure, building a depth first traversal tree,
using the depth first traversal tree to answer questions on
connectivity and paths between pairs of vertices.
See dfs1.java and
- Week 8 (10/10-10/14): A simple array based implementation of the
Stack data structure, recursive implementation of depth first
traversal, analysis of depth first traversal.
- Week 9 (10/17-10/21): Linked lists.
See Lafore's Link class and his
- Week 10 (10/24-10/28): Applications of linked lists: adjacency list
representation, hashing with chaining.
- Week 11 (10/31-11/4): More on hashing: using chaining to avoid
collisions, some thumb rules for picking good hash functions,
efficient implementation of hash functions.
Read Chapter 11 (pages 519-528, 552-574).
- Week 12 (11/7-11/11): Priority queue ADT, binary heaps.
Read Chapter 12.
- Week 13 (11/14-11/18): Dijkstra's shortest path algorithm. Read pages 687-707 from
Chapter 14. Also, read Project 3 handout.
- Week 14 (11/28-12/2): Binary search trees and tree traversals. Read Chapter 8.
- Week 15 (12/5-12/9): Balanced binary search trees; red-black trees. Read Chapter 9.