CSE 12: Summer Session I (2012) -- Basic Data Structures and Object-oriented Design

Course staff

Jake Whitehill (Lecturer)Ruixin Yang (TA)Kerwin Azares (Tutor)Yuta Morinaga (Tutor)Kimberly Chu (Tutor)Susan Liu (Tutor)Dustin Yu (Tutor)Wilson Guo (Tutor)
jake-at-mplab-dot-ucsd-dot-edur4yang-at-cs-dot-ucsd-dot-edukazares-at-ucsd-dot-eduymorinag-at-ucsd-dot-eduk4chu-at-ucsd-dot-edusuliu-at-ucsd-dot-edudusti-dot-yu-at-gmail-dot-comwiguo-at-ucsd-dot-edu

Webpage

Click here.

Textbook

There is no required textbook for this class. However, you may find the following textbook useful, and it's free: Data Structures in Java for the Principled Programmer, by Duane Bailey.

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

Unannounced Quiz 0 from Lecture 1 -- solution.
Unannounced Quiz 1 from Lecture 5 -- solution.
Extra Practice 1 -- specification.

Midterm

Here is the midterm and how it was graded.

Topics:

Practice midterm.

Final exam

Problems:
  1. Short answer
  2. Lists -- write code
  3. Correct/incorrect code snippets of stacks/queues/lists
  4. BSTs -- write code
  5. Hash tables
  6. Algorithmic complexity and time cost analysis
Practice final.
Solution to practice final's findLowestCommonAncestor

Discussion section

Discussion sections will be led by Ruixin Yang:
Tuesdays, 11:00-11:50amWLH 2113
Tuesdays, 4:00-4:50pmWLH 2113
Wednesdays, 1:00-1:50pmCENTER 203

Office hours

I will be serving lab hours (see schedule below). If you would like an office appointment (CSE 2216), please email me.

Lab hours

Lab hours are held in CSE 240/250/260. See schedule here.

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 dateOther materials
P0: Hello Whirled
 Tue 3 July 2012 at 11:59pm
P1: Doubly-linked lists, tester, and vegetable; also, see hints (extended to) Sun 15 July 2012 at 11:59pmConfetti.java; Grading test code
P2: Queues using ring buffers Sun 22 July 2012 at 11:59pm Grading test code
P3: d-ary heaps extended to Mon 30 July 2012 at 11:59pm Grading test code 1, Grading test code 2
P4: Mystery data structures Thu 2 August 2012 at 11:59pm My solution

Grading

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

Syllabus

Class # Date Topics Slides Projects due Suggested reading
Week 1: introduction to data structures; lists; unit testing; object orientation in Java
1 Mon 2 July 2011 Introduction to data structures; administrivia L1
2 Tue 3 July 2011 Abstraction; abstract data types; interface versus implementation; lists. L2 P0 Bailey, ch. 3
3 Wed 4 July 2011 HOLIDAY
4 Thu 5 July 2011 Java Virtual Machine (JVM); linked lists L3 Bailey, ch. 9
Week 2: stacks and queues; generic types in Java; algorithmic complexity analysis
5 Mon 9 July 2011 More on linked lists. L4 Bailey, ch. 8
6 Tue 10 July 2011 L5 Bracha: Generics in the Java Programming Language, sections 1-5.
7 Wed 11 July 2011 Object-orientation in Java (interfaces, classes, abstract classes, inner classes, anonymous classes) L6 Oracle docs on casting; Bailey, ch. 4
8 Thu 12 July 2011 Type-safety, Java Generics P1 (extended to Sunday, July 15)
Week 3: heaps; trees; recursive data structures
9 Mon 16 July 2011 Stacks and queues L7 Bailey, ch. 10
10 Tue 17 July 2011 Midterm examination (in class) -- MAKE SURE YOU BRING YOUR STUDENT ID WITH YOU.
11 Wed 18 July 2011 Algorithmic analysis L8
12 Thu 19 July 2011 More on algorithmic analysis; compareTo L9 Bailey, ch. 11
Week 4: binary search trees; AVL trees; hash tables; caches
13 Mon 23 July 2011 Binary search; trees; heaps L10 Bailey, chs. 12-13
14 Tue 24 July 2011 More on heaps. L11 Bailey, ch. 14
15 Wed 25 July 2011 More on Java Generics; binary search trees (BSTs) L12
16 Thu 26 July 2011 Hash tables L13 Bailey, ch. 15
Week 5: graphs; sorting
17 Mon 30 July 2011 Caches, graphs. L14 Bailey, ch. 16
18 Tue 31 July 2011 More on graphs, sorting. L15
19 Wed 1 Aug 2011 More on sorting. L16
20 Thu 2 Aug 2011 Even more on sorting, final exam review L17
21 Sat 4 Aug 2011 Final examination -- MAKE SURE YOU BRING YOUR STUDENT ID WITH YOU.