W1004

Final Review

Created by @don4yu

Instructions

Navigate through slides with up/down, left/right arrows
Press ESC to see an overview of all slides available
Questions are based on actual final questions seen in years past and should be attempted

Algorithms

Be able to read pseudocode
Be able to understand and solve for big-O notation
Pay special attention to sorting algorithms

What is the runtime for the following pseudocode (assume A is an array)?

for i = 0 to length(A)
	int sum = 0;
	for j = i to length(A)
		sum += j;
	A[i] = sum;

Answer

Answer = O(n^2)

O(n^2) <- because we have one for loop that runs n times and within that for loop we run another for loop that runs ~n-1, n-2, n-3,...,1 times. This is about n(n-1)/2 computable steps which is O(n^2) *only count the highest-order term for big-O

Selection Sort

Searches for the minimum element at each interval and puts that in the front of the unsorted portion of the list

Find minimum value Swap with first unsorted value That value is now sorted. Repeat steps 1-2

Runtime is O(n^2)

Which of the following is a possible intermediate state for the list {11, 7, 5, 2} during selection sort?

{11, 7, 5, 2} {11, 5, 2, 7} {2, 7, 5, 11} {2, 11, 7, 5} Answer

Answer = #3 {2, 7, 5, 11}

We find the minimum element and swap it with the first non-sorted element (here we found the minimum element 2 and swapped it with 11).

Insertion Sort

Swap two adjacent elements if necessary as you go through the list leftwards. At each iteration you find the first unsorted element and keep swapping it leftwards until it is inserted into the right place.

Check first 2 elements and swap if necessary Move one step to left and repeat step 1 & 2 until you reach the beginning of the list or if you reach a point where a swap is not necessary First element now sorted and repeat with still unsorted elements

Runtime is O(n^2)

Insertion Sort Question

What state is the list {4, 1, 6, 2} in after the 3rd step in the insertion sort algorithm?

{1, 4, 6, 2} {1, 2, 4, 6} {1, 4, 2, 6} {2, 1, 6, 4} Answer

Answer = #3 {1, 4, 2, 6}

{1,4,2,6} <- we first swap 4 and 1 we then see 4 and 6 and don’t need to swap them; we then swap 2 and 6.

*Note answer could be {1, 2, 4, 6} if we are considering passes in the algorithm rather than steps. After the first pass the list is now {1, 4, 6, 2} and after the second pass it is still {1, 4, 6, 2} and after the third pass it is {1, 2, 4, 6}

Other Algorithms

Linear Search - O(n)
Binary Search - O(logn)
Bubble Sort - O(n^2)

Which of the following is the big-O runtime for doing a search on an unsorted list?

O(logn) O(n) O(n^2) O(n logn) Answer

Answer = #2 O(n)

We can just do a linear search on an unsorted list. (note that sorting it and then doing a binary search would take longer)

Java

Arrays and ArrayLists
Classes, Inheritance, Polymorphism
File IO
Exceptions

Arrays

Think of arrays as cabinets! You can put your shoes inside them.

Holds a specific number of elements (cannot grow!)
All elements must be of the same type
Indexes start at 0 not 1

//array of 10 ints
int[] myNumbers = new int[10];
//access 2nd element
int x = myNumbers[2];

ArrayList

Resizable array (don't need to worry about the size of the array anymore!)

Example Question: Which of the following snippets of Java code will work properly?

int[] arr;

arr[0] = 6;

int[] arr = new int[5];

arr[5] = 6;

int[] arr = new int[5];

arr[0] = 3;

Answer

Answer = #3

Choice #1 is incorrect because you have to initialize an array first. Choice #2 is incorrect because the last element of an array is at len(array) - 1.

More Java

Booleans and Constructing Circuits

Know how to construct truth tables Know how to read and construct truth expressions Know how to draw circuits

Example Question: For what values of P and Q is the expression below false?

(NOT (P and Q) and NOT(P or NOT Q))

P = T, Q = T P = T, Q = F P = F, Q = F All of the above Answer

Answer = #4 (All of the above)

P Q P ^ Q NOT (P ^ Q) P v NOT Q NOT (P v NOT Q) (NOT (P ^ Q) and NOT (P v NOT Q)) 1 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0

We see that the expression is only true for P=False and Q=True

Gates

AND gate = 3 transistors
OR gate = 3 transistors
NOT gate = 1 transistor

Example Question: If I have a circuit with 2 AND gates, 2 NOT gates, and 5 OR gates, how many transistors will I need?

9 23 17 15 Answer

Answer = #2 (23)

2 * 3 + 2 + 5 * 3 = 23

Parts of a Computer

Primary Memory
Control Unit
ALU
I/O

Example Question: Suppose a machine language uses op codes that are 4 bits long. What is the maximum number of distinct instrutions this language could have?

16 4 8 256 Answer

Answer = #1

16 <- 2^4 possible instructions

Networks

It's important to remember the network layers. A short mnemonic is provided.

Application (all)
Transport (teachers)
Network (need)
Data Link (data)
Physical (processing)

Computer Network Concepts

Types of networks (star, bus, ring, etc.)
UDP vs. TCP
Examples protocols within each layer
What are Collisions?
ARQ algorithm

Questions

1. Which of the following is a protocol of the application layer?

HTTP QRS ARQ XXX PHP Answer

Answer = HTTP

HTTP is an application layer protocol for sending data across the Web. Other application layer protocols that are important are FTP, SMTP.

2. Which of the following is not a standard layer of the internet?

Transport Network Computer Application Answer

Answer = #3

Computer is not a layer.

Djikstra's Algorithm

Think of it as a greedy algorithm
At every step you will find the node that takes the LEAST work to get to and analyze it
After you analyze a node (find everything that it's connected to) you don't have to consider it anymore
Remember that you do NOT update a node if we find a new but longer route to a node
- If you had to write a 10 page essay, and then your professor asks you if you would rather write a 12 page essay, would you make the switch?

Given the above graph. What is the 4th node that we analyze under Djikstra's algorithm?

F D E C Either D or E Answer

Answer

Either D or E (at this stage of djikstra's algorithm it takes the same amount of steps to get to either D or E and so we could analyze either to get the shortest path)

CS Theory

What does a Turing Machine (model of a computing agent) need to exhibit?
- well-ordered collection
- unambiguous and effectively computable operations
- halts in finite time
- produces a result
Understand Church-Turing Thesis - if there exists an algorithm to do a symbol manipulation task, then there exists a Turing Machine to do that task

Turing Machines

Make sure that you are able to read and understand Turing Machine instructions (Current State, what you read, what you write, next state, movement)
Example - (1, 0, 1, 2, R) <- If I am in state 1 and I see a 0, I'll write a 1 there and go to state 2 by moving right.

Question

What do the following instructions do on the following tape?

(1, 1, 0, 1, R)

(1, 0, 1, 1, R)

(1, b, b, 2, L)

(2, 1, 1, 2, L)

(2, 0, b, 2, L)

b11000b

Answer

Keep pressing down arrow for steps. Bold symbol is where the tape is point at.

b01000b in state 1

b00000b in state 1

b00100b in state 1

b00110b in state 1

b00111bb in state 1

b00111b in state 2

b0b111b in state 2

bbbb111b in state 2

Answer is b111b. Remember that blanks extend infinitely on both sides.

More Review

Last Year

Life After W1004

Join ADI
Join CORE
Continue CS Curriculum
?????
Profit (though Happiness is more important)

THE END

Questions? Short Speeches?

Please email me at dy2212@columbia.edu if you have questions, complaints, constructive criticism!

W1004 – Final Review – Algorithms

donyu

W1004 – Final Review – Algorithms

0 0 (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/platform.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();

w1004_review

W1004

Final Review

Instructions

Algorithms

Answer = O(n^2)

Selection Sort

Answer = #3 {2, 7, 5, 11}

Insertion Sort

Insertion Sort Question

Answer = #3 {1, 4, 2, 6}

Other Algorithms

Answer = #2 O(n)

Java

Arrays

ArrayList

Answer = #3

More Java

Booleans and Constructing Circuits

Answer = #4 (All of the above)

Gates

Answer = #2 (23)

Parts of a Computer

Answer = #1

Networks

Computer Network Concepts

Questions

Answer = HTTP

Answer = #3

Djikstra's Algorithm

Answer

CS Theory

Turing Machines

Question

Answer

More Review

Life After W1004

THE END

Questions? Short Speeches?

0 0