CE 221: Data Structures
and Algorithms
01: Introduction
1
Book
Read sections 1.1 to 1.3 in Weiss, Data Structures and Algorithm Analysis in Java
2
Instructor: Prof. Dr. Cem Evrendilek
● [Link]
● Office: A 311
● Office Hours: available via Blackboard
● Contact: via e-mail
○ [Link]@[Link]
3
Course
● Syllabus: [Link]
○ Link to syllabus available also via Blackboard
● Lectures and Labs
○ Section 1: on Mondays (8:30-11:05) at M 303 (LAB hours: 14:00-15:40 at ML 201)
○ Section 4: on Wednesdays (13:05-15:40) at C 403 (LAB hours: 8:30-10:10 at ML 105)
● Book: M. A. Weiss, Data Structures and Algorithm Analysis in Java, 3/e, Pearson, 2012,
978-0132576277
● Evaluation:
○ Lab: 40%, Midterm: 20%, Final: 40%
○ Lab: 2 Lab quizzes and 6 Lab programming assignments. A total of 8 graded assignments each with 5%
● Lab and lecture schedule available via Blackboard. Lab Assistant: Semih YAĞCI (Yes, the
labs are to be held this week)!
4
Course Policy
● Conduct:
○ Labs always in Java programming language, and exam questions in Java as well as in
pseudocode.
○ Each assignment starts and ends in the same lab session. Late assignments will not be
accepted.
● Policy:
○ No tolerance on academic dishonesty
○ Plagiarism, copying, cheating, outsourcing the assignment to another person or organization
with or without pay are considered as actions of academic dishonesty
○ Failure to maintain academic honesty may result in disciplinary action according to the Izmir
University of Economics’ disciplinary bylaw for students of institutions of higher education
([Link]
○ Repeating cheating cases will cause a disciplinary action
5
Labs
● You will be given a lab assignment
○ to be completed at the end of the lab session
○ to be done individually
● No resources except for ones given in Blackboard
○ No Internet access!
● You should
○ implement your solution in Java
○ make sure that it compiles
○ test it with some test cases
● We will test your code with wide range of test cases
● We will check for unusual similarities in submissions
○ If your code gets flagged, the score is 0
6
Q&A
● Can I study with my friend(s) to solve the assignments/labs/exams?
○ No. All assignments/labs/exams should be done individually.
○ You shouldn’t be sharing any of your answers in any circumstance.
○ It is better not to contact to anyone during an assignment/lab/exam.
● I found a resource with a similar answer online. Can I copy and paste or
paraphrase it?
○ No. It is plagiarism. You should use your own answer.
● Can I post the questions online and get them solved with or without pay?
○ No. It is highly unethical. You cannot share the assignments/labs/exams that belong to the university
online without permit.
● Can I study from the book and online resources for the course?
○ Yes. In fact, I strongly recommend you to study from the book.
○ Questions in the assignments/labs/exams will be similar to ones asked before but relatively new.
7
Introduction
● See that how a program performs for reasonably large input is just as
important as its performance on moderate amounts of input
● Summarize basic mathematical background needed
● Review recursion
8
Motivating Examples: Selection
● Selection problem: you have a random sequence of N numbers and would
like to determine the k th largest.
○ read them into an array. Sort them in decreasing order. Return the k th element.
○ read the first k elements into the array. Sort them in decreasing order. Next read the remaining
elements one by one. If the new element read is smaller than the last, ignore it otherwise place
in the correct spot in the array bumping one element out of the array.
● A simulation with a random file of 30 million elements and k = 15,000,000
shows that each requires several days of computer processing.
9
Motivating Examples: Word Puzzles
● Solving a popular word puzzle: Input consists of a
two-dimensional array of letters and a list of words.
The objective is to find the words lying horizontally,
vertically or diagonally in either direction.
1. for each word in the word list, check (row, column,
orientation)
2. for each ordered quadruple (row, column, orientation,
number of characters), test whether the word is in the word
list.
● {this, two, fat, that}
10
Math Review: Exponents
11
Math Review: Logarithms
● In computer science, all logarithms are to the base 2 unless specified
otherwise.
Definition:
Theorem:
Proof:
12
Math Review: Logarithms
Theorem:
Proof:
13
Math Review: Logarithms
14
Math Review: Series
● Geometric Series
● if 0 < A < 1, then
as N tends to ∞, the sum approaches 1/(1-A)
15
Math Review: Series
We can derive the last formula by
16
Math Review: Series
We can use this same technique to compute
17
Math Review: Series
Arithmetic series
18
Math Review: Series
● When k = −1, the formula is not valid. We then need another formula
● Harmonic number HN
● The error in the preceding approximation tends to γ ≈ 0.57721566, which is known as Euler’s constant.
19
Math Review: Series
General algebraic manipulations:
20
Math Review: Modular Arithmetic
● We say that A is congruent to B modulo N, written
A ≡ B (mod N),
if N divides A − B.
○ The remainder is the same when either A or B is divided by N
● Example: 81 ≡ 61 ≡ 1 (mod 10)
● if A ≡ B (mod N), then
○ A + C ≡ B + C (mod N) and AD ≡ BD (mod N)
21
The P Word
● There are various ways of proving statements in data structures analysis
● Proof by Induction: It has two standard parts:
○ The first step is proving a base case. Establishing that a theorem is true for some small
(usually degenerate) value(s). This step is almost always trivial.
○ Next, an inductive hypothesis is assumed. Generally, this means that the theorem is
assumed to be true for all cases up to some limit k. Using the assumption, the theorem is then
shown to be true for the next value, typically k+1.
22
The P Word
● Example: Prove that Fibonacci Numbers F0 =1, F1 =1, and
Fi = Fi-1 + Fi-2 for i > 1, satisfy Fi < (5/3)i for i ≥ 1.
● Proof: :
○ Verify that the theorem is true for the trivial cases (base cases):
F1 =1 < (5/3)1 and, F2 = 2 < (5/3)2 . These prove the basis.
○ We now assume that the theorem is true for i = 1, 2, ..., k ; this is the inductive hypothesis. To
prove the theorem, we need to prove Fk+1 < (5/3)k+1
23
The P Word
Fk+1 = Fk + Fk-1
24
The P Word
● Example: If N ≥ 1 then
● Proof: For the base case, the theorem is true when N = 1.
● For the inductive hypothesis, assume the theorem is true for 1 ≤ k ≤ N. Let’s try
to prove that it is true for N + 1
● We have
25
The P Word
26
The P Word
● Proof by Counterexample: Best way for proving that a statement is false.
● Example: The statement Fk ≤ k2 is false.
○ The easiest way to prove this is to compute F11 = 144 > 112 = 121
27
The P Word
● Proof by Contradiction:
○ It proceeds by assuming that the theorem is false and showing that this assumption implies
that some known property is false, and hence the original assumption is erroneous.
● Example: Prove that there is an infinite number of primes.
● Proof: Assume the theorem is false, so that there is some largest prime Pk .
Let P1, P2 ,..., Pk be all the primes in order and consider N = P1P2…Pk + 1.
Clearly, N > Pk , so by assumption N can not be prime.
● However, none of P1, P2 ,..., Pk divides N exactly, because remainders are
all 1.
This is a contradiction: numbers are either prime or a product of primes.
Hence the original assumption is false implying that the theorem is true.
28
A Brief Introduction to Recursion
● A function that is defined in terms of itself is called recursive. Not all
mathematically recursive functions are correctly or efficiently implemented
by recursion.
● Example: f(x) = 2f(x − 1) + x2 for all integers x ≥ 1 with f(0)=0
29
A Brief Introduction to Recursion
● Example: f (x) = 2f(x − 1) + x2 for all integers x ≥ 0 with f(0)=0
● If f is called with a value of 4, then 2*f(3)+4*4 will be required to be
computed. Thus, a call is made to find f(3). f(4)=2*f(3)+4*4,
f(3)=2*f(2)+3*3, f(2)=2*f(1)+2*2, f(1)=2*f(0)+1*1, f(0)=0 base case.
Recursive calls until a base case. f(-1)=? Automatic Bookkeeping 30
Recursion: Bad
● bad(0)=0, bad(N)=bad(N/3 + 1) + N-1
● To compute bad(1), the computer will repeatedly make calls to bad(1).
Eventually, it will run out of space
31
Fundamental Rules of Recursion
1. Base cases: You must always have some base cases, which can be solved
without recursion.
2. Making progress: For the cases to be solved recursively, the recursive call
must always be to a case that makes progress toward a base case.
3. Design rule: Assume that all the recursive calls work. This rule is important.
It relieves you of the burden of thinking about the details of bookkeeping.
4. Compound interest rule: Never duplicate work by solving the same instance
of a problem in separate calls. Hidden bookkeeping costs are mostly
justifiable. However; It should never be used as a substitute for a simple loop.
32
Recursion: Induction
printOut(N) prints out positive integers. printDigit(Ch)takes a single digit
number as character and output it to the terminal.
Theorem: Recursive number-printing algorithm is correct for N ≥ 0.
Proof (by induction): If N has one digit, then it is correct. Assume it works for all
numbers of k or fewer digits. A number N of k+1 digits is expressed by its first k
digits followed by its least significant digit, respectively.
By the inductive hypothesis, first part is printed correctly and then the last digit is
appended.
33
Homework
● 1.5, 1.7, 1.8.a, 1.8.b, 1.8.c, 1.9, and 1.12.
● You are requested to study and solve the exercises . Note that these are for
you to practice only. You are not to deliver the results.
34
References
● CE221 Lecture Slides by Prof. Dr. Cem Evrendilek
● Data Structures and Algorithm Analysis in Java, Third Edition, Mark Allen
Weiss
● Edited by Assoc. Prof. Dr. Kaya Oğuz