cs61b-sp18 - aviatesk

This repository is for aviatesk's self-learning of algorithms and data structure with the materials for CS61B, taught at UC Berkeley in Spring 2018 by Josh Hug.

Beyond of all, I really, really appreciate this great learning-materials are made public, and want to say an infinite thanks to the instructor Josh and everyone who contributed to his lectures.

Archives

Week	Note	Discussion	Examprep	Lab	Project / Homework
1	Lec.1: Intro to Java, Static Typing Lec.2 Class	disc1	N/A	lab1: javac, java, git (More git: Using Git)	hw0: Basic Java Syntaxes
2	Lec.3: References Lec.4: Node Based List, Nested Class, Caching, Sentinel Lec.5: Generics, Array	disc2: Pointer, Naked Linked List (Squaring)	examprep2	lab2: Debugger, JUnit Test	proj0: Just Fun with Java
3	Lec.6: Array-based List Lec.7: Testing Lec.8: Interface, Implementation Inheritance, Dynamic Method Selection	disc3: Linked List, Array	examprep3: Naked Linked List (Insertion, Reversing)	lab3: Debugger, JUnit Test, Naked Linked List	proj1a: Doubly-linked List, Doubly-linked Array
4	Lec.9: Implementation Inheritance, Encapsulation, Type Checking, Higher Order Lec.10: Subtype Polymorphism Lec.11: Libraries	disc4: Inheritance	examprep4: Inheritance, Type Checking	lab4: Not available for ppl alone ...	proj1b: Test Driven Development proj1glod: Randomized Tests
5	Lec.13: Conversion, Immutability, Generics Lec.14: Exception, Iterator	disc5: ADTs	examprep5: Using ADTs	lab5: Pseudo random number	hw1: Package, Interface, Generics, Exception, Iteration
6	Lec.15: Package, Access Control, Object method Lec.16: Programming Efficiency, API design, Views (No note but the slides available at link)	disc6: Access Control, Designing API	examprep6: Exception, Linked List	lab6: Interactivity within StdDraw	proj2 phase1: Large scale programming, Generative program using pseudo random number
7	Lec.17: Introduction to Asymptotic Analysis, Big Theta Lec.18: 5 Basic Case Studies of Asymptotic Analysis Lec.19: Big O, Big Omega, Amortized Analysis	disc7: Asymptotic Analysis Examples, Using ADTs	examprep7: (A bit too much exam-flavored) AA Problems	N/A	proj2 phase2: UI Design, Serialization
8	Lec.20: Disjoint Set Lec.21: Binary Search Tree Basics Lec.22: Tree Rotation, B-Tree, LLRB	disc8: AA of Pseudo Code, Mathematical Discussion of AA	examprep8: AA of Pseudo Code	N/A	hw2: Percolation Simulation with Disjoint Set
9	Lec.23: Hashing Lec.24: Priority Queue, Heap, Data Structure Summary Lec.25: Tree Traversal, Pruning, Quadtree	disc9: BST Validation, 2-3 Tree Review, Hashing	examprep9: Hashing: Runtime, Function, Consistency with equals()	lab9: BSTMap & (Naïve) HashMap	hw3: Hash Function
10	Lec.27: Graph Introduction Lec.28: DFS (including Topological Sort), BFS	disc10: Easy Quiz(Heap, Tree-Traversal, Quadtree)	examprep10: Tree properties	lab10: Binary Min-Heap	N/A
11	Lec.29 Lec.30 Lec.31	disc11: Graph Algorithm Design	examprep11: Graph Traversal Application	lab11: BFS, Cycle Check, A* (Optional TODO: Completing MazeAStarPath.java remaining)	hw4: A* Implementations (Optional TODO: Implementing neighbors() method in Word.java, which works in constant time, remaining)
12	Lec.32: Basic Sorts Lec.33: Quick Sort Lec.34: Sort Stability, Shuffling	disc12	examprep12	lab12: Merge/Quick Sort on Queue	N/A

Bugs and fixes

• proj0: Some characters in proj0/StdDraw.java could not be compiled on my environment
  • Fix: 94c2ade

$ javac NBody.java

.\StdDraw.java:299: error: unmappable character (0x92) for encoding windows-31j
 *  You save your image to a file using the <em>File 竊? Save</em> menu option.
                                                      ^
.\StdDraw.java:433: error: unmappable character (0x93) for encoding windows-31j
 *       from (0.5, 窶?&infin;) to (0.5, &infin;) may not be visible even in the
                     ^

.\StdDraw.java:1190: error: unmappable character (0x93) for encoding windows-31j
     * (<em>x</em><sub><em>n</em>窶?1</sub>, <em>y</em><sub><em>n</em>窶?1</sub>).
                                  ^
.\StdDraw.java:1190: error: unmappable character (0x93) for encoding windows-31j
     * (<em>x</em><sub><em>n</em>窶?1</sub>, <em>y</em><sub><em>n</em>窶?1</sub>).
                                                                      ^
.\StdDraw.java:1219: error: unmappable character (0x93) for encoding windows-31j
     * (<em>x</em><sub><em>n</em>窶?1</sub>, <em>y</em><sub><em>n</em>窶?1</sub>).
                                  ^
.\StdDraw.java:1219: error: unmappable character (0x93) for encoding windows-31j
     * (<em>x</em><sub><em>n</em>窶?1</sub>, <em>y</em><sub><em>n</em>窶?1</sub>).
                                                                      ^
Note: .\StdDraw.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
6 errors

Java versions (on Windows 10)

$ java -version

java version "11.0.2" 2018-10-16 LTS
Java(TM) SE Runtime Environment 18.9 (build 11.0.2+7-LTS)
Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11.0.2+7-LTS, mixed mode)

Links

• Course web-page: https://sp18.datastructur.es/index.html
• The original cloned skeleton repository: https://github.com/Berkeley-CS61B/skeleton-sp18
• Autograder: https://www.gradescope.com/

Who I am

KADOWAKI, Shuhei - Undergraduate@Kyoto Univ. - aviatesk