Learn Algorithm

Algorithms                       Tushar Gahora             

What you will get:
・Intermediate-level survey course.
・Programming and problem solving, with applications.
・Algorithm: method for solving a problem.
・Data structure: method to store information. 

topic

Why study algorithms?

Their impact is broad and far-reaching. 

Internet. Web search, packet routing, distributed file sharing, ... Biology. Human genome project, protein folding, ... 

Computers. Circuit layout, file system, compilers, ... 

Computer graphics. Movies, video games, virtual reality, ... Security. Cell phones, e-commerce, voting machines, ... 

Multimedia. MP3, JPG, DivX, HDTV, face recognition,  ...

Social networks. Recommendations, news feeds, advertisements, ... Physics. N-body simulation, particle collision simulation, ...

・Study of algorithms dates at least to Euclid. 

・Formalized by Church and Turing in 1930s. 

・Some important algorithms were discovered by undergraduates in a course like this!

                                     “ Algorithms + Data Structures = Programs.” 

 

• To solve problems that could not otherwise be addressed.
• For intellectual stimulation.
• To become a proficient programmer.
• They may unlock the secrets of life and of the universe. Computational models are replacing math models in scientific inquir.
• 
  

• 
  
• Their impact is broad and far-reaching. 
• Old roots, new opportunities. 
• To solve problems that could not otherwise be addressed. 
• For intellectual stimulation. 
• To become a proficient programmer. 
• They may unlock the secrets of life and of the universe. 
• For fun and profit.

Prerequisites

• Programming: loops, arrays, functions, objects, recursion.
• Java: we use as expository language.
• Mathematics: high-school algebra.

Programming environment

• Use your own, e.g., Eclipse.

Introduction

We're going to concentrate on programming and problem solving in the 

context of real applications, and our focus is going to be on two things,

Algorithms which are methods for solving problems and data structures which store 

the information associated in problem, with a problem and go hand in hand with 

algorithms. These are the basic topics that we'll cover in part one and part two 

of the course. The first part is data type sorting and searching. We'll consider a 

number of data structures and algorithms that are basic to all the methods we 

consider including stacks, queues, bags and priority queues. Then we'll consider 

classic algorithms for sorting, putting things in order. That's quicksort, 

mergesort, heapsort and radix sorts. And we'll consider classic methods for 

searching. Including binary search trees, red-black binary search trees and hash 

tables. The second part of the course is for more advanced algorithms including 

graph algorithms, classic graph searching algorithms, minimum spanning tree and 

shortest path algorithms, algorithms for processing strings including regular 

expressions and data compression. And then some advanced algorithms that make use of 

the basic algorithms that we developed earlier in the course. So, why should one 

study algorithms? Well, their input, impact is very broad and far-reaching. 

From the internet to biology to, commercial computing, computer graphics, 

security, multimedia, social networks, and scientific applications, algorithms are 

all around us. They're used for movies and video games, for particle collision 

simulation, they're used to study the genome, and all manner of other 

applications. So, that's one important reason to study algorithms, their impact 

is broad and far-reaching. Algorithms are also interesting to study, because they, 

they have ancient roots. Now the first algorithm we studied goes back to 300 

B.C., dating at least to Euclid. The concept of an algorithm was formalized 

actually here at Princeton, by Church and Turing, in the 1930s. But most algorithms 

that we consider, were discovered in recent decades. In fact, some were 

discovered by undergraduates in a course, course like this. And there's plenty of 

other algorithms waiting to be discovered by students like you. The main reason that 

people study algorithms, is to be able to solve problems that it could not otherwise 

be addressed. For example, in the first lecture, we're going to talk about the 

network connectivity problem, where the problem is, given a large set of items 

that are connected together pairwise is there a way to get from one to another 

with a path through the connections. As you can see from this example, it's not 

clear whether or not there's such a path, we need a computer program to do it, in 

fact, we need an efficient algorithm to do it. In this case the answer is that there 

is such a path. Another reason to study algorithms is for intellectual 

stimulation. Algorithms are very interesting objects to study. Don Knuth 

who wrote several books on, on algorithms and was a pioneer in the field said that, 

"An algorithm must be seen to be believed." You can't just think about an 

algorithm you have to work with it. Another quote from Francis Sullivan, says, 

"The great algorithms are the poetry of computation." Just like verse, they can be 

terse, elusive, dense, and even mysterious. But once unlocked, they cast a 

brilliant new light on some aspect of computing. Algorithms are interesting for 

intellectual stimulation. Another reason many people study algorithms and I suspect 

many of you, is it's necessary to understand good algorithms, efficient 

algorithms, a good data structures in order to be a proficient programmer. Linus 

Torvalds, who created lin, Linux, says that the difference between a bad 

programmer and a good one is whether he considers his code or his data structures 

more important. Bad programmers worry about the code, good programmers worry 

about data structures, and their relationships. And, I might add, the 

algorithms that process them. Niklaus Wirth, another pioneer in computer 

science, wrote a famous book called Algorithms + Data Structures = Programs. 

[cough]. Another reason nowadays to study algorithms is that, they have become a 

common language for understanding, nature. Algorithms are computational models, and 

algorithmic models are replacing mathematical models in scientific inquiry. 

In the twentieth century, math, scientists developed mathematical models to try to 

understand natural phenomenon. It soon became clear that those mathematical 

models were difficult to solve. It was difficult to create solutions, to be able 

to test hypotheses against natural phenomenon. So, more and more and more now 

a days people are developing computational models, where they attempt to simulate 

what might be happening in nature in order to try to better understand it. Algorithms 

play an extremely important role in this process. And we'll see some examples of 

this in this course. Another important reason is that if you know effect, how to 

effectively use algorithms and data structures you're going to have a much 

better chance at interviewing for a job in the technology industry then if you don't. 

So, here's a bunch of reasons that I just went through for studying algorithms. 

Their impact's broad and far-reaching, they have old roots and present new 

opportunities, they allow us to solve problems that could not otherwise be 

addressed, you can use them for intellectual stimulation to become a 

proficient programmer. They might unlock the secrets of life in the universe, and 

they're good for fun and profit. In fact, a pr ogrammer might ask, why study 

anything else? Well, there's plenty of good reasons to study other things, but 

I'll submit there's no good reason not to study algorithims. [cough] So, for this 

course we have two resources that I want to talk about and make sure that people 

are familiar with before entering into the content. 

We will provide much more detail information 

on that as we get into the assignments. You can use your own programming 

environment if your comfortable with.

Union−Find-  We illustrate our basic approach to developing and analyzing algorithms by considering the dynamic connectivity problem. We introduce the union–find data type and consider several implementations (quick find, quick union, weighted quick union, and weighted quick union with path compression). Finally, we apply the union–find data type to the percolation problem from physical chemistry.

Analysis of Algorithms-  The basis of our approach for analyzing the performance of algorithms is the scientific method. We begin by performing computational experiments to measure the running times of our programs. We use these measurements to develop hypotheses about performance. Next, we create mathematical models to explain their behavior. Finally, we consider analyzing the memory usage of our Java programs.

Programming Assignment: Percolation. Your programming assignment will give you an opportunity to apply these concepts to a fundamental problem in physical chemistry. It is the first of many examples where a good algorithm—in this case, weighted quick union—makes the difference between being able to efficiently solve a problem and not being able to address it at all.

Job Interview Questions.Algorithmic interview questions based on the lecture material.

1.1 UNION-FIND

Steps to developing a usable algorithm. 

・Model the problem. 

・Find an algorithm to solve it. 

・Fast enough? Fits in memory?

 ・If not, figure out why.

 ・Find a way to address the problem. 

・Iterate until satisfied.

‣ dynamic connectivity
 ‣ quick find
 ‣ quick union
 ‣ improvements
‣ applications

Dynamic connectivity

Given a set of N objects.

• Union command: connect two objects

• Find/connected query: is there a path connecting the two objects?

• union(4, 3) union(3, 8) union(6, 5) union(9, 4) union(2, 1)

connected(0, 7)     x

 connected(8, 9)    ✔

 union(5, 0) 

union(7, 2)

 connected(0, 7)

 union(1, 0)

 union(6, 1)   ✔ 

Modeling the objects

Applications involve manipulating objects of all types. 

・Pixels in a digital photo.
 ・Computers in a network
. ・Friends in a social network.
 ・Transistors in a computer chip
. ・Elements in a mathematical set.
 ・Variable names in Fortran program.
 ・Metallic sites in a composite system.

When programming, convenient to name objects 0 to N –1.

 ・Use integers as array index. 

・Suppress details not relevant to union-find.

                                        Modeling the connections

We assume "is connected to" is an equivalence relation: 

・Reflexive: p is connected to p. 

・Symmetric: if p is connected to q, then q is connected to p. 

・Transitive: if p is connected to q and q is connected to r, then p is connected to r. Connected components. Maximal set of objects that are mutually connected.

Implementing the operations

Find query. Check if two objects are in the same component. 

Union command. Replace components containing two objects with their union.