Course: CS61B | EECS at UC Berkeley Skip to main content Toggle navigation EECS at UC Berkeley Main menu AboutToggle submenu for About About Overview By the Numbers Diversity History Special Events Visiting AcademicsToggle submenu for Academics Academics Overview Undergraduate Admissions & Programs Graduate Admissions & Programs For Current Students Courses ResearchToggle submenu for Research Research Overview Areas Centers & Labs Colloquium BEARS Symposium PeopleToggle submenu for People People Overview Directory Leadership Faculty Students Staff Alumni ConnectToggle submenu for Connect Connect Overview Support EECS K-12 Outreach Recruit Students Student Affairs Faculty Positions Contact Secondary menu Home For Students For Faculty/Staff Industry News Events Give Toggle Search Search form Search Search Home Academics Courses CS61B CS 61B. Data Structures Catalog Description: Fundamental dynamic data structures, including linear lists, queues, trees, and other linked structures; arrays strings, and hash tables. Storage management. Elementary principles of software engineering. Abstract data types. Algorithms for sorting and searching. Introduction to the Java programming language. Units: 4.0 Prerequisites: COMPSCI 61A, COMPSCI 88, or ENGIN 7. Credit Restrictions: Students will receive no credit for COMPSCI 61B after completing COMPSCI 61BL, or COMPSCI 47B. A deficient grade in COMPSCI 61B may be removed by taking COMPSCI 61BL. Formats: Fall: 3.0 hours of lecture, 1.0 hours of discussion, and 2.0 hours of laboratory per week Spring: 3.0 hours of lecture, 1.0 hours of discussion, and 2.0 hours of laboratory per week Summer: 6.0 hours of lecture, 2.0 hours of discussion, and 4.0 hours of laboratory per week Grading basis: letter Final exam status: Written final exam conducted during the scheduled final exam period Class Schedule (Fall 2021): MoWeFr 1:00PM - 1:59PM, Internet/Online – Anjali Kantharuban, Henry Maier, Linda Deng, Paul HILFINGER Class homepage on inst.eecs General Catalog listing Department Notes: In CS 61B, students are expected to gain facility with Java programming, become familiar with fundamental data structures and algorithms, and learn techniques for constructing programs of moderate size using Java. Roughly a third of the semester will be devoted to an introduction to Java. Constructs and topics to be covered include the following: The compile/execute cycle. Primitive data types (integer, floating point, character, boolean); arrays; classes. Interactive control structures. Functions; recursion; overloading. Inheritance; interfaces; exceptions; threads. In the rest of the semester, and in conjunction with practice of basic Java programming techniques, students will implement and experiment with fundamental algorithms and data structures: Construction, modification, and traversal of linked list structures of various forms -- singly-linked, doubly-linked, and circular, with and without sentinels. Construction, modification, and traversal of binary trees (in particular, binary search trees and expression trees). Sorting of sequences by selection, insertion, quicksort, merge sort; binary search through a binary search tree of a sorted sequence. Binary heaps. Hashing. Elementary graph structures and algorithms. The aim is for students to be able to recognize when these data structures and algorithms are applicable to a problem, and to be able to evaluate their relative advantages and disadvantages. Design in terms of abstract data types and isolation of their implementation in modules will be emphasized. We intend that, having taken CS 61B, student will: understand the distinction between a specification or interface and an implementation; understand pre- and post-conditions in specifications; be able to use a specification expressed as a set of procedure headers with comments; and be able to provide suitable comments for modules, data types, and functions. Data types used for illustration will include queues, stacks, dictionaries, sets, and GUI toolsets. CS 61B is the first place in our curriculum that students design and develop a program of significant size (1500-2000 lines) from scratch. Course assignments typically involve two such programs. CS 61A is an important prerequisite for 61B. We expect to build heavily on data-oriented and object-oriented design approaches introduced in those courses, as well as on algorithms for recursive list and tree manipulation. Related Areas: Programming Systems (PS) Home About History Diversity Visiting Special Events Academics Undergrad Admissions & Programs Graduate Admissions & Programs Courses Prospective Women Students Current Students Research Areas Centers & Labs Projects Technical Reports PhD Dissertations Joint Colloquium BEARS Symposium People Directory Leadership Faculty Staff Students Alumni Resources Room Reservations My EECS Info For Students For Grads For Undergrads GSIs/Readers/Tutors IT Services Facilities/Safety For Faculty/Staff Visiting Scholars Industry CAP Entrepreneurial Activity Connect Support Us K-12 Outreach Faculty Positions Contact Home EE CS UC Berkeley Berkeley Engineering Accessibility Nondiscrimination Privacy Berkley EECS on Twitter Berkeley EECS on Instagram Berkeley EECS on LinkedIn Berkeley EECS on YouTube © 2021 UC Regents Privacy Policy
