CSE 12: Summer Session II -- Basic Data Structures and Object-oriented Design

Course staff

Jacob (Jake) Whitehill (Lecturer): jake-at-mplab-dot-ucsd-dot-edu
Vineet Kumar (TA): vkumar-at-cs-dot-ucsd-dot-edu
Anthony Dang (Tutor/Grader): a6dang-at-ucsd-dot-edu
Kerwin Azares (Tutor/Grader): kazares-at-ucsd-dot-edu
Stephanie Yeh (Tutor/Grader): yehstephanie-at-gmail-dot-com

Textbook

There is no required textbook for this class. However, you might find the following textbook helpful for getting an alternative perspective on the subject matter: Data Structures Outside In with Java, by Sesh Venugopal. Pearson/Prentice Hall, 2007.

Moodle forum

In order to receive important course communication, you will need to monitor the CSE 12 Moodle forum. Note: For the CSE 12 Moodle Forum, log in with your UCSD email account name and password, instead of your "cs12" account name. The Account Lookup Tool will tell you your email account name, and your cs12 account name. (If you are a "summer session" student, you will need to sign up for an account, which you can do here.)

In-class quizzes and exercises

Exercise 1
Quiz 1
Quiz 2
Midterm Practice 1
Midterm Practice 2
Midterm Practice 3
Midterm Practice 4
Proof that two iterators will intersect in linked list with loop
Exercise 2
Quiz 3
Some practice questions for the final exam

Discussion section

Discussion sections will be led by Vineet Kumar and will take place in York 3000A on Thursday at 1pm and Friday at 1pm.

Office/lab hours

Office hours (Jake): Tu 1-2pm, Wed 1-2pm, Thu: 2-3pm in CSE 2106. You can also email me to set up an alternative time.

UPDATED lab hours (for last week): Lab hours are held in the CSE labs (B230) in the basement of the CSE building (EBU3B).
Tutor Sun Mon Tue Wed Thu Fri
Jake 1-3pm
Vineet 12-6pm 1-4pm 1-3pm
Kerwin 3-7pm 1-4pm
Anthony 3-6pm 6-10pm 6-8pm
Stephanie 3-7pm 1-4pm 3-5pm 2-4pm

Programming projects

To complete the programming assignments you will need to make sure to have a CSE 12 account on the ieng6.ucsd.edu server. See this page (courtesy of Paul Kube) for more information.

ProjectDue date
P0: Hello Whirled
 Wed 3 Aug 2011 at 11:59pm
P1: Linked Lists and Confetti
 Mon 8 Aug 2011 at 11:59pmP1 hints
P2: Generics and Unit Testing
 Mon 15 Aug 2011 at 11:59pm Supplementary slides on junit by Vineet
P3: Queues using ring buffers
 Mon 22 Aug 2011 at 11:59pm
P4: d-ary Heaps
 Mon 29 Aug 2011 at 11:59pm
P5: Mystery Data Structures
 Wed 31 Aug 2011 at 11:59pm

Grading

ComponentProportion
Programming assignments 45%
Midterm examination 20%
Final examination 30%
Class participation (Moodle forum + in-class quizzes) 5%

Syllabus

Class # Date Topics Slides Projects due Suggested reading
Introduction to data structures; linear data structures; object-oriented design
1 Mon 1 Aug 2011 Introduction to data structures; administrivia PDF Venugopal: Preface; 1.1-1.4; 2.
2 Tue 2 Aug 2011 Abstraction; abstract data types; lists. PDF None
3 Wed 3 Aug 2011 Java Virtual Machine; Java memory management; linked lists PDF P0 Venugopal: 4.5-4.7
4 Thu 4 Aug 2011 More on linked lists; iterators PDF None.
5 Mon 8 Aug 2011 Object-orientation in Java; more on iterators PDF P1 without iterators Bracha: Generics in the Java Programming Language, sections 1-5. Also, Venugopal: 1.13.
6 Tue 9 Aug 2011 Type-safety; Java generics PDF
7 Wed 10 Aug 2011 More on Java generics; asymptotic cost analysis; empirical cost analysis (benchmarking) PDF and PDF from Paul Kube P1 with iterators Venugopal: 3.
8 Thu 11 Aug 2011 More on asymptotic cost analysis; more on empirical analysis; stacks and queues PDF Venugopal: 6, 7.
9 Mon 15 Aug 2011 More on queues PDF P2
10 Tue 16 Aug 2011 Midterm examination (in class) -- MAKE SURE YOU BRING YOUR STUDENT ID WITH YOU.
Searching algorithms and supporting data structures
11 Wed 17 Aug 2011 Recursion. PDF Venugopal: 8.
12 Thu 18 Aug 2011 Binary trees; heaps PDF Venugopal: 9, 11
Sorting algorithms and supporting data structures
13 Mon 22 Aug 2011 More on heaps; binary search trees PDF P3 Venugopal: 10
14 Tue 23 Aug 2011 More on BSTs; AVL trees. PDF
15 Wed 24 Aug 2011 More on Java generics; explanation of P5 PDF
16 Thu 25 Aug 2011 Hash tables PDF Venugopal: 12
Miscellany
17 Mon 29 Aug 2011 More on hash tables; caches and LRU replacement; graphs PDF P4
18 Tue 30 Aug 2011 More on graphs; Kevin Bacon Number; sorting PDF
19 Wed 31 Aug 2011 More on sorting PDF P5
20 Thu 1 Sep 2011 Even more on sorting; Reece's peanut butter cup(s); review for final exam. PDF
21 Fri 2 Sep 2011 Final examination (11:30am - 2:29pm, Peter 104)