Transcript intro-0 - UCSB Computer Science

CS 130 A: Data Structures and Algorithms
0

Course webpage: www.cs.ucsb.edu/~suri/cs130a/cs130a

Email: [email protected]

Office Hours: 11-12 Wed
CS 130A: Prerequisites
First upper division course
 More in-depth coverage of data structures and algorithms


1
Prerequisites
 CS 16: stacks, queues, lists, binary search trees, …
 CS 40: functions, recurrence equations, proofs, …
 Programming competence assumed
 C, C++, and UNIX
 Refresh your coding and debugging skills
 Use TAs
Text Book
Data
Structures & Algorithm Analysis in C++
by Mark Allen Weiss
Supplemental
material from Introduction to Algorithms,
by Cormen, Leiserson, Rivest, Stein [MIT book]
Lecture
material primarily based on my notes
Lecture notes available on my webpage
See web page for lectures updates, assignments.
2
CS 130 A: Grade Composition
2 Midterm exams (30% total)
 2 Programming assignments (30% total)
 1 Final exam (40%)


Homework assignments
 They will not be graded: they are to help you practice
problem solving and prepare for exams
 Solving homework problems key to understanding.
 Solutions will be made available, so you can self-assess your
understanding and work with TAs to correct your mistakes.
Attend all lectures!
 Schedule is tentative.
3  Unexpected changes in midterm/exam dates

Some Advice and Caution
Posted schedule of lectures, assignments, exams is tentative
 Reviews unplanned
 Unexpected events may change dates of midterms
 No makeup exams, no extensions.

Attend all lectures.
 Read lecture notes (material) before coming to class.

4
Teaching Assistants

Teaching Assistants:
 Bay-Yuan Hsu ([email protected])



Semih Yavuz ([email protected])


5
Discussion: Wed 6:30-7:200 (GIRV 1119)
TA hours: Mon 4-6 (Trailer 936)
Discussion: Tues 6:30-7:20 (GIRV 1116)
TA hours: Tues 3:30-5:30 (Trailer 936)
Discussion Sections


No discussion section this week
Discussion Format
 No new material discussed
 It is meant as a help session
 Use them to go over homework assignments
 Programming pointers

6
But TA are not there to help you write or debug code
What the course is about

The course is primarily about Data Structures

Algorithms covered in small part (20%)

CS 130B is the main algorithms course

7
Data structures will be motivated by applications although
we won’t discuss them in any detail
What the course is about

This is a Theory course, not programming/systems




Primary focus on concepts, design, analysis, proofs
Includes 2 coding assignments, but no programming taught
C++, Unix competence expected
My teaching philosophy for 130A
 Discovery and insights. Big picture.
 Best understood in abstract form, with pen-paper
 Alternative Style: learn by coding. (If coding is your thing, feel
free to program the data structures.)


8
Exams on conceptual understanding, not coding details.
Homework exercises model for exam questions.
Course Outline
Introduction and Algorithm Analysis (Ch. 2)
 Hash Tables: dictionary data structure (Ch. 5, CLRS)
 Heaps: priority queue data structures (Ch. 6)
 Balanced Search Trees: general search structures (Ch. 4.1-4.5)
 Union-Find data structure (Ch. 8.1–8.5, Notes)
 Graphs: Representations and basic algorithms
 Topological Sort (Ch. 9.1-9.2)
 Minimum spanning trees (Ch. 9.5)
 Shortest-path algorithms (Ch. 9.3.2)
 B-Trees: External-Memory data structures (CLRS, Ch. 4.7)
 kD-Trees: Multi-Dimensional data structures (Notes, Ch. 12.6)
 Misc.: Streaming data, randomization (Notes)

9
What are your goals?
A step towards the BS degree
 Just a required CS course
 Becoming a well-rounded computer scientist
 Intellectual (theory) aspects of CS
 Clever ideas
 Interview questions at elite software companies

10
My goals
Algorithms is my research expertise
 A lively and enormously active area of research
 Broad impact on almost every area of CS

My personal mission:
 transmit some of the knowledge and enthusiasm
 Win the best teacher award
 Weekly Jokes
 Send me your jokes!

11
Why Study Algorithms and Data Structures?

12
Intellectual Pursuit
Why Study Algorithms and Data Structures?

13
To become better computer scientist
Why Study Algorithms and Data Structures?

14
World domination
Algorithms are Everywhere









15
Search Engines
GPS navigation
Self-Driving Cars
E-commerce
Banking
Medical diagnosis
Robotics
Algorithmic trading
and so on …
Emergence of Computational Thinking
Computational X
Physics: simulate big bang, analyze LHC data, quantum computing
Biology: model life, brain, design drugs
Chemistry: simulate complex chemical reactions
Mathematics: non-linear systems, dynamics
Engineering: nano materials, communication systems, robotics
Economics: macro-economics, banking networks, auctions
Aeronautics: new designs, structural integrity
Social Sciences, Political Science, Law ….
Emergence of Computational Thinking
Modern World of Computing
Age of Big Data, birth of Data Science
 Digitization, communication, sensing, imaging…
 Entertainment, science, maps, health, environmental, banking…

Volume, variety, velocity, variability
 What all happens in 1 Internet minute?

18
19
Intelligent Computational Systems
20
Why Data Structures?



Data is just the raw material for information, analytics,
business intelligence, advertising, etc
Computational efficient ways of analyzing, storing, searching,
modeling data
For the purpose of this course, need for efficient data
structures comes down to:




21
Linear search does not scale for querying large databases
N2 processing or N2 storage infeasible
Smart data structures offer an intelligent tradeoff:
Perform near-linear preprocessing so that queries can be
answered in much better than linear time