Algorithms:

It is just a set of instructions

or steps we are going to
take to perform a particular
task or to solve any
problem. In more simple
words, it determines our
course of action to do any
activity. Now, an algorithm
cannot be just any course of
action or set of steps. There
are few things to take care
of;
• It must be correct
• It must be the most
ef cient way to tackle the
certain activity or problem
fi
 • It must be the most
ef cient way to tackle the
certain activity or problem
• It must be swift
• It must be easy to
understand and manage
later
All the problems we have
been solving so far included
different algorithms that we
wrote to solve certain
problems. Like for example
an algorithm we wrote to
nd all uppercase letters in
an array or to nd all small
letters, to nd any
punctuation marks etc. We
have been particularly using
if else statements for such
code under a loop. So
fi
fi
fi
fi
fi
fi
fi
fi
 punctuation marks etc. We
have been particularly using
if else statements for such
code under a loop. So
together, all of our code to
nd something that we
intend to, was an algorithm
for that problem. Now, you
can take the nal result as a
destination. That destination
has many paths, some are
easy, some are steep some
are just bread and butter.
Some takes less time to
reach, some take more.
Some are easy to
remember and navigate
later, while some are not.
But all paths leads to the
same destination. So we
fi
fi
fi
fi
fi
fi
fi
 remember and navigate
later, while some are not.
But all paths leads to the
same destination. So we
can call all paths as
algorithms(unless it leads
us to wrong destination),
but not every path is same.
It’s our duty to gure out the
most ef cient, swift and
easy to understand path to
reach the destination. It is
an example of a good
algorithm. In our previous
example of is-else
statements, we were
searching for a number. A
computer runs
methodologically, if we gave
it an algorithm, it will follow
fi
fi
fi
fi
fi
fi
fi
 searching for a number. A
computer runs
methodologically, if we gave
it an algorithm, it will follow
it as it is no matter what. It
can access only one
memory location at a time.
i.e the elements in the
memory one at a time only.
So it’s like all the elements
are behind close doors in
the memory and the
computer can open one
door at a time. Now it’s
upon us that how we make
it open those doors to do
our task. We can make it
open the doors one-by-one
from left or right side, we
can make it open the door
fi
fi
fi
fi
fi
fi
fi
 our task. We can make it
open the doors one-by-one
from left or right side, we
can make it open the door
from middle and then make
comparison and many other
ways as well.
Search Algorithms:
An algorithm in which we
search some thing from the
memory location is called
search algorithm. Again we
know that it can access only
one memory location at a
time. So we must
implement an ef cient
algorithm. There are few
different types of search
algorithms;
fi
fi
fi
fi
fi
fi
fi
fi
algorithm. There are few
different types of search
algorithms;
Linear Search:
It is a sort of search
algorithm where we search
each element of the list one
by one until it matches our
intended one. So it checks
each memory location one-
by-one either from left side
or right side. But it will not
break the order which is
given in the algorithm. It
checks each element all the
way to end(unless it nds
the desired one in the
middles
fi
fi
somewhere) and if not
matched, it returns false. It
is usually slow but less
complex to implement. It is
best to use when the
elements are not arranged
in an order or we just dont
know the order. So then it’s
obvious that it should check
each element one-by-one. It
can also be used for smaller
list(lesser elements). On the
other hand, if our list is
small(it has very few
elements) then its also the
best to implement the linear
search even if we know the
order of arrangement of
elements) then its also the
best to implement the linear
search even if we know the
order of arrangement of
elements because it is very
easy to implement then
other types of search
algorithms. So linear search
is best when we dont know
the order of arrangements
of elements or even if we
know the order, if the
elements are very few then
it’s again the best approach.
Its pseudocode is;
For each door from left to
right
if 50 is behind that door
 return true
Return false
Binary search:
It is a sort of search
algorithm which works on
“Divide and conquer”
strategy. This algorithm
takes big jumps and make a
comparison between
elements. This is best to
implement when we know
for sure the order or
arrangement of the
elements. So if we know the
arrangement, we can
obviously compare different
elements and see if our
desired element is ahead of
fi
fi
arrangement, we can
obviously compare different
elements and see if our
desired element is ahead of
out or behind it. What it
does is that instead of
checking one-by-one, it
jumps right straight to the
middle. It analyses the
middle element, if its not our
desired one then it compare
that with the middle
element. If our desired
element is ahead of the
middle one, then it jumps
halfway through on the right
side again. But if it was
behind the middle element,
then it had jumped halfway
through on the left side. It
fi
fi
side again. But if it was
behind the middle element,
then it had jumped halfway
through on the left side. It
again repeats the same
algorithm until it nds the
desired element. If it checks
all the doors and the
element it not there then it
returns false. This algorithm
is very fast but dif cult to
implement. We ca only
implement it if we know the
arrangement of elements. It
is however, very swift. So its
better then linear search if
we know the arrangement
and the list is large. Let’s
take an example, if we have
a list of natural numbers
fi
fi
we know the arrangement
and the list is large. Let’s
take an example, if we have
a list of natural numbers
from 1 to 100 and they are
in the same order. So now
we know the arrangement
and the list is large. Our
desired number is 90. So
the best approach here
would be binary search
because we know the
arrangement and list is big.
We will start by jumping to
the middle, which is 50.
Now we will compare our
desired number and 50 and
it is clear that 90 is ahead of
50. So the numbers(or
elements) left now are 50,
fi
fi
desired number and 50 and
it is clear that 90 is ahead of
50. So the numbers(or
elements) left now are 50,
so halfway through 50 is 25.
Hence we will land on 75.
Comparison again, 90 is
greater. Jump halfway
through again on right side.
This time a half way jump
will get us to 87. Again 90 is
greater, halfway jump again,
it’s 93 now. Now, as we
compare, we see that 93 is
left behind. So we will jump
halfway through on left side.
But wait, now half way of 93
that would be 46 again. We
will jump halfway through
the elements covered in last
fi
fi
But wait, now half way of 93
that would be 46 again. We
will jump halfway through
the elements covered in last
jump. So we covered 6
elements last time, halfway
to 6 is 3. We will go 3
elements behind and loo!
We landed on 90. We
reached 90 on just 5 to 6
jumps. Now think about
linear search, we would
have needed 90 jumps to
get there or if from right side
10 which is still slower the
this algorithm. Yes! This is
complex but very swift. One
thing to remember is that if
we jumped ahead of our
desired element, and we
fi
fi
complex but very swift. One
thing to remember is that if
we jumped ahead of our
desired element, and we
have to go back. We will not
jump halfway through on left
side those number of
elements again. We will go
halfway through the
elements we have covered
in the last jump so if we
have covered 10 elements
in last jump, we will go 5
elements behind this time
even if we are on 50th
element. Its pseudocode is;
For every doors from left
to right
fi
fi
 if no doors left
return false
if 50 is behind
doors[middle]
return true
else if 50 <
doors[middle]
search doors[0]
through doors[middle - 1]
else if 50 >
doors[middle]
search doors[middle
+ 1] through doors[n - 1]
Return statement:
A return statement when
used in any function other
than main function, it
returns the control to
A return statement when
used in any function other
than main function, it
returns the control to
function call of that
particular function. With the
control, this return function
return a value to the
function call as well. That
value is usually written with
this function in this way;
return n;
However, if this return
function is used inside of
main function, it does not
return the control to any
function call. Rather it
terminates the program at
that very point where it is
used. Inside main, we also
 function call. Rather it
terminates the program at
that very point where it is
used. Inside main, we also
give it a value. That value is
sometimes referred to as
“Exit status”. When
terminated, this value is not
shown on the output. But if
use a special code, which is
“echo $?”, we can see the
value or exit status
assigned to return.
Running time:
We have talked earlier
about the algorithm being,
not only correct but ef cient
and swift. But how are we
going to determine which
algorithm is more ef cient
fi
fifi
fifi
fi
fi
 not only correct but ef cient
and swift. But how are we
going to determine which
algorithm is more ef cient
than the other. We can like
guess but thats obviously
not the best approach. Also
what is the factor, on the
basis of which we are
making that guess. Turns
out the factor is running
time. It is not a time in terms
of second or minutes rather
it is actually the number of
basic operations the
compiler performs to solve
a speci c problem and
different tasks within that
problem. This is the
deciding factor as to which
fi
fi
fi
fifi
fi
fi
 a speci c problem and
different tasks within that
problem. This is the
deciding factor as to which
algorithm is better than the
other. Obviously, the
algorithm with less running
time is better because it just
takes less operations to do
a speci c task. Now we
cant just guess that which
algorithm has a better
running time. So there are
mathematical formulas for
different algorithms. These
formulas use asymptotic
notations in with some
variables and mathematic
functions. In these formulas,
we use the total number of
fi
fi
fi
fifi
fi
fi
 notations in with some
variables and mathematic
functions. In these formulas,
we use the total number of
operations it is going to
perform mingled with any
mathematical function that
de nes the nature of that
particular algorithm. We
dont usually get very
pedantic with these
formulas like we just have
to make an approximate
expression to compare
different algorithms. We
dont have to be very
precise. We can make a
formula or expression and
than from that expression,
eliminate all terms except
fi
fifi
fifi
fi
fi
 precise. We can make a
formula or expression and
than from that expression,
eliminate all terms except
the most powerful one like
an exponential function or a
factorial or a logarithmic
function. The asymptotic
notations are used to
describe this not-very-
precise formula like using
such notations tells us that
we are just making a vague
idea oof the algorithm and
not everything is very down
to detail. It also describes
upper bound or lower bound
of the algorithms. The upper
bound is the maximum
number of operations it is
fi
fifi
fifi
fi
fi
 upper bound or lower bound
of the algorithms. The upper
bound is the maximum
number of operations it is
going to perform to solve
any particular problem. It is
like the worst case
scenario. The notation used
for upper bound is big O’
“O”. We write the big O and
then inside parenthesis, we
write the mathematical
expression to de ne the
algorithm. Lower bound is
the minimum number of
operations it is going to
perform to solve any
particular problem. It is like
the best case scenario. The
notation used for lower
fi
fifi
fi
fi
fi
fi
 perform to solve any
particular problem. It is like
the best case scenario. The
notation used for lower
bound is big Ω(omega) “Ω”.
We write the big Ω and then
inside parenthesis, we write
the mathematical
expression to de ne the
algorithm. There is a third
notation called big theta(we
use the capital theta sign).
This is used if the number
of operations for best case
scenario and worst case
scenario are same. This
notation is very rarely used.
The examples of such
running time formulas is;
fi
fifi
fi
fi
fi
fi
 notation is very rarely used.
The examples of such
running time formulas is;
O(n); upper bound for liner
search
O(log n); upper bound for
binary search
Ω(1); lower bound for both
linear and binary search.
These are some of basic
examples. We can form our
own formulas according to
the nature of algorithm. We
dont have to be very
rigorous. Moreover, if with
n(number of total
operations), there is any
single constant is being
multiplying, dividing,
substracting or added, we
fi
fifi
fifi
fi
fi
operations), there is any
single constant is being
multiplying, dividing,
substracting or added, we
can just omit it. We just
have to write the crucial
mathematical functions or
any other variables being
used in our algorithm. There
are some very basic
runtime formulas that can
be used for ,most of
algorithms;
O(n^2)
O(n log n)
O(n)
O(log n)
O(1)
 These can be used with
lower bound or theta as well
just by changing notation
signs.
These running time may
seem trivial thing but its
very crucial. Because a
good programmer cares
about his time while writing
large programs so he must
be able to comprehend and
understand that which
running time is better
between different
algorithms that can be used
for that problem to save his
time. So while solving
problems, we must make it
fi
fi
fi
 algorithms that can be used
for that problem to save his
time. So while solving
problems, we must make it
a habit to determine and
compare the running time of
different algorithms that we
are considering and then
use the most swift and
ef cient algorithm. If we
dont make it a habit now, to
would cause problems in
future. Try to form running
time formulas and then
compare them. You will
make mistakes, it will cause
you unease but thats worth
the pain in long term
because eventually you will
learn. This running time is
fi
fi
fi
 you unease but thats worth
the pain in long term
because eventually you will
learn. This running time is
affected by the
input(number of tasks we
have to perform). The larger
the input, the greater the
running time. It also depend
upon the machine. Some
machines are more ef cient
than the others. The
formula is actually a relation
between operations being
done to perform the tasks.
i.e. a relation between
operations and tasks.
Practice making these
formulas on a page rst by
writing all tasks to be done
fi
fi
fi
 operations and tasks.
Practice making these
formulas on a page rst by
writing all tasks to be done
and then analysing n by
going over the tasks
manually. Analyse all the
operations and make a
formula. Then eliminate all
constants and smaller
functions, just keep the
biggest, most powerful
function with any asymptotic
notations. We can also
analyse any code written
and make a formula. Just
do some calculations on
total number of steps that
you see on screen being
done. Dont speculate
fi
fi
fi
 do some calculations on
total number of steps that
you see on screen being
done. Dont speculate
things, just keep in mind the
operations you see on the
screen. First of all, go for
any loop or nested loops.
The number of steps a loop
takes is explicitly written on
the loop, just subtract one
from that number i.e. if
steps on loops are n, the
actual number of steps
would be n-1.This is if the
loop is starting from 0, if it is
starting from anything other
then 0 then we will take the
number of steps as it
is(without subtracting 1).
fi
fi
fi
 starting from anything other
then 0 then we will take the
number of steps as it
is(without subtracting 1).
Then if there is any nested
loop inside of that loop, take
its total steps and multiply
them with that of outer
loops. Then look for other
loops and take their number
of steps. Note: we only
have to multiply the number
of steps of network of
nested loops with each
other. For separate loops,
we must add their number
into each other. Then look
for single steps. Take all
single steps separately and
add all the number of single
fi
fi
fi
 into each other. Then look
for single steps. Take all
single steps separately and
add all the number of single
steps into each other and
into total number of steps of
all loops. We will have an
expression. Now eliminate
all constants and smaller
functions, just keep one
most powerful function only,
written with asymptotic
notation.
String comparison:
If we want to compare two
strings to check their
equality, we cannot use
“==“ operator or compare
them like we compare
integers. There is a very
fi
fi
fifi
fi
fi
fi
fi
fi
fi
fi
fi
 equality, we cannot use
“==“ operator or compare
them like we compare
integers. There is a very
technical reason for that but
we will discuss it later.
Another more trivial reason
is that an integer is a single
value, it is like a single
character so we can
compare it with another
character because
“==“ operator is used to
compare single
characters(or values) with
each other. But as we know,
a string is not a single value
or characters. It is an array
of multiple characters so
just by using this
fi
fi
fifi
fi
fi
fi
fi
fi
 a string is not a single value
or characters. It is an array
of multiple characters so
just by using this
“==“ operator, we cannot
compare them all because it
can comparere just one
character. Wd can however
use a loop and iterate over
each character of a string
and do the work but thats
just not very practical and
the code gets messy. So
there is a special function
for this purpose. It is found
in string.h library. The
function is “strcmp(a, b)”.
This is a very powerful
function for comparison of
two strings as it can return 3
fi
fi
fifi
fi
fi
fi
fi
fi
 function is “strcmp(a, b)”.
This is a very powerful
function for comparison of
two strings as it can return 3
sort of answers. It does not
just test the equality of two
strings, it also checks that if
a string is ASCII-betically
behind or ahead the other
string. ASCII-betically
means that it does not
check the order
alphabetically rather it test it
according to the
arrangement of characters
in ASCII chart on the basis
of their ASCII values. It
follows the standard ASCII
order of values assigned to
different characters. It
fi
fi
fifi
fi
fi
fi
fi
fi
 of their ASCII values. It
follows the standard ASCII
order of values assigned to
different characters. It
compares the ASCII values
of each character of both
strings till the rst non-
matching character or NULL
character is found. It
terminates right away at the
rst non-matching
character. It returns 0 if all
the characters in all indexes
of both strings are literally
equal. It returns an integer
less then 0 if string ‘a’ is
ASCII-betically behind
string ‘b’ and returns an
integer greater then 0 if
string ‘a’ is ASCII-betically
fi
fi
fifi
fi
fi
fi
fi
fi
 ASCII-betically behind
string ‘b’ and returns an
integer greater then 0 if
string ‘a’ is ASCII-betically
ahead string ‘b’. It checks
all the indexes of string ‘a’
with the corresponding
indexes of string ‘b’. When
the rst non-matching
character is found, the
strcmp() function terminates
right away. Hence, it makes
its decision about greater or
lesser ASCII value
character on the basis of
rst non-matching
character. If the rst non-
matching character of string
‘a’ is behind that of
corresponding character of
fi
fi
fifi
fi
fi
fi
fi
fi
 character. If the rst non-
matching character of string
‘a’ is behind that of
corresponding character of
‘b’ , it will terminate right
away and returns a
negative value. It won’t
check for the rest of values
after the rst non-matching
character is found. If the
corresponding value of ‘a’ is
greater than that of ‘b’, it
terminates right away and
return integer greater then
0. It only keeps checking if
the corresponding values
are same. The moment the
rst non-matching value
comes, it terminates. It can
actually return any number
fi
fi
fi
fi
fi
fi
fi
fi
fi
 are same. The moment the
rst non-matching value
comes, it terminates. It can
actually return any number
less then or greater them 0
for respected cases. This is
not a random number. It
calculates the difference of
both ASCII values of the
rst non-matching
characters and return their
difference. It always put
ASCII value of character of
string ‘a’ rst and than that
of ‘b’. Thats why we get a
positive number if value of
‘a’ is ahead that of ‘b’(a has
greater ASCII value) and we
get a negative number if
value of ‘a’ is behind that of
fi
fi
fi
fi
fi
fi
fi
fi
fi
 ‘a’ is ahead that of ‘b’(a has
greater ASCII value) and we
get a negative number if
value of ‘a’ is behind that of
‘b’(a has smaller ASCII
value). This is just a little
overview of this function.
We will discuss this in-depth
later. As for now, just think
that this function compare
two strings and checks their
equality.
- A rule in programming is
that if we are working with
numbers and as long as we
dont have to do any proper
mathematical calculation on
those numbers(like not on
the ascii values but proper
numerical calculations
fi
fi
fifi
fi
fi
fi
fi
fi
mathematical calculation on
those numbers(like not on
the ascii values but proper
numerical calculations
which returns a numerical
answer), then it is better to
use those numbers inside of
a string. So just make a
string os such numbers.
User-de ned Data
types(Structs):
These are custom data
types that user de nes in
their function according to
their needs. This is a new
data type which is actually a
combination of different
data types. A user can
customise it in any way they
want. Different data types
fi
fi
fi
combination of different
data types. A user can
customise it in any way they
want. Different data types
can be used to build this
new single custom data
type. Then using this
custom data type, we can
give a variable myriad
different data types as
inputs i.e. now we can
strore, inside of a single
variable, values of different
data types hich we can use
separately wherever we
want. This concept is more
of like sub-variables, where
you can store inside a
variable, different sub-
variables, even of different
fi
fi
of like sub-variables, where
you can store inside a
variable, different sub-
variables, even of different
types. We must de ne
these custom data type
before calling it, either
before main function or
inside of it. Its basic syntax
is;
typedef struct
{
declare as many sub-
variables as you can
here(each in separate line)
even with different data
types.
}
fi
fi
 name of data type;
This is the basic syntax of
de ning a user-de ned data
type. Typedef and struct are
keywords which are written
always as they are. Inside
of curly braces, we can
declare all the sub-
containers with different(or
same) data types, each in
separate line, ending with a
semi colon. After curly
braces, declare the name of
the new custom data type.
Using this is very
interesting, declare a
variable with the data type
you have de ned. Then
fi
fi
fi
fi
fi
 Using this is very
interesting, declare a
variable with the data type
you have de ned. Then
store values in that variable
inside of different sub-
containers you have
created while de ning. You
must declare the variable
with that custom data type
rst and then store values in
sub-variables
separately.You will do
this(store values/initialise
values into sub-variables)
by using a ‘.’(dot) operator.
After name of variable, use
a dot and then the name of
that sub-container. Then
initialise a value in that sub-
fi
fi
fi
fi
fi
 After name of variable, use
a dot and then the name of
that sub-container. Then
initialise a value in that sub-
container. Do that will sub-
containers and store values.
Now all those values belong
to a single variable but
inside of that variable,
different sub-variables
contain them hence they
can be used differently. Or
they can only be used
differently. We cannot use
the single variable as a
whole expecting that it
would print all the values.
Example of such a program
is;
fi
fi
fi
fi
fi
 would print all the values.
Example of such a program
is;
int main()
{
typedef struct
{
string name;
int age;
long number;
} person;
person a;
a.name = ("Saif
Ali");
a.age = 19;
a.number =
923145687432;

printf("%s\n%i\n%li\
n", a.name, a.age,
a.number);
fi
fi
fi
fi
fi
printf("%s\n%i\n%li\
n", a.name, a.age,
a.number);
}
Here, we have used three
different data types to build
a single custom data type.
Then used that data type
inside of a single variable
and stored different
values(of different data
types) using different sub-
containers in to the variable.
We can also declare an
array using custom data
types hence we can make
an array of variables of sub-
variables as well. i.e.;
types hence we can make
an array of variables of sub-
variables as well. i.e.;
typedef struct
{
string name;
int age;
long number;
} person;
int main()
{
person a[3];
a[0].name =
("Sardar Saif Ali");
a[0].number =
923213452897;
a[0].age = 19;
a[1].name =
("Aimash Hassan
Sabri");
 a[1].name =
("Aimash Hassan
Sabri");
a[1].number =
92342874534;
a[1].age = 19;

printf("%s\n%li\n%i\
n%s\n%li\n%i\n",
a[0].name,
a[0].number,
a[0].age, a[1].name,
a[1].number,
a[1].age);
}
This is an example of array
declared with custom data
type. Now we can make an
array of arrays(2d array) of
different variables(simple
array) of different sub-
 type. Now we can make an
array of arrays(2d array) of
different variables(simple
array) of different sub-
variables(UDT).
UDT stands for user-
de ned types. This
technique is very useful for
making les about
information of people in a
structured way. The
probability of error is very
less and we can store all
information about a
particular person at one
place. These custom data
types can have unlimited
sub-containers. This is a
genuine toolkit of ‘c’ and
involve no abstraction by
fi
fi
fi
 types can have unlimited
sub-containers. This is a
genuine toolkit of ‘c’ and
involve no abstraction by
cs50 team(just when using
string data type but thats an
overall abstraction which
can be compensated for
array of characters). So far,
we must declare the
variable with custom data
type rst(separately) and
then initialise different
values to its different sub-
variables using ‘.’ operator
with variable name and then
sub-variable name(each
separately) like we did in
above examples. We
cannot declare the data
fi
fi
fi
 sub-variable name(each
separately) like we did in
above examples. We
cannot declare the data
type and then store values
in its sub-variables on same
line(atleast not yet). Structs
are very useful if we want to
store multiple pieces of
information about a single
object.
- If we want to print the
ASCII value of any
character(like the numeral
ASCII value of any
alphabetical character or
anything inside strings), the
character must be a single
character. Not as a whole
string. We can declare char
fi
fi
fi
anything inside strings), the
character must be a single
character. Not as a whole
string. We can declare char
type for single character
and do this or if we want to
do this with the characters
inside of a string, we must
use their separate indexes.
i.e.
string a = “Hi!”;
printf(“%i\n”, a[0]);
We can do this with other
characters as well but we
must use a separate format
speci er and use each
character separately with
their index. Calculations(on
ASCII values) also cannot
be performed on whole
fi
 character separately with
their index. Calculations(on
ASCII values) also cannot
be performed on whole
strings. We must use the
characters separately with
their indexes. In short, if we
want to perform any
operation on a string related
to their ASCII value(which is
an integer), we must use
characters of that string
separately.
Sorting:
Sorting is a process of
arranging a set of data in
any particular manner. We
can arrange the data in any
manner like alphabetically,
date added, date modi ed
fi
fi
fi
fi
fi
fi
fi
 any particular manner. We
can arrange the data in any
manner like alphabetically,
date added, date modi ed
etc. Sorting is useful when
we have to search for some
data again and again.
Obviously if we have to
search any data only once,
why would we bother taking
all that pain for
implementing an algorithm
for sorting and then
searching for that data? But
if we have any data which
we have to search for again
and again, implementing an
algorithm for sorting rst is
actually useful. Because if
data is sorted we can us
fi
fi
fi
fi
fi
fi
 and again, implementing an
algorithm for sorting rst is
actually useful. Because if
data is sorted we can us
more ef cient and swift
search algorithms like
binary search. So if
searching is to be done
again and again, we should
sort the data rst in any
particular manner. There
are different sorting
algorithms that we can use.
Some are easy to
implement but a little
tedious while some are
dif cult to implement but
ef cient and swift.
fi
fi
fi
fi
fi
fi
 Selection sort;
In this sorting algorithm, the
control iterates over the
whole set of data. While
iterating, it checks for the
smallest number(or smallest
item according to our
sorting manner), when it
has nished iterating, it
swaps the smallest item it
got at the end with the rst
item of the list. Then it starts
the iteration again, but this
time, from i+1 item(it ignore
the swapped item every
time as i is incremented). It
iterates over the whole list
again and at the end, the
fi
fi
fi
 the swapped item every
time as i is incremented). It
iterates over the whole list
again and at the end, the
smallest item it has is
swapped with the rst item
which i+1 item this time. It
repeats the same process
again and again until all the
data is sorted. Every time, it
starts from ahead the
already swapped item(i is
incremented every time). It
is one of those algorithms
which are relatively easy to
implement but very slow.
Like it iterates over the
same data again and again.
Its running time is Θ(n^2).
i.e. in best and worst case
fi
fi
fi
 Like it iterates over the
same data again and again.
Its running time is Θ(n^2).
i.e. in best and worst case
scenario, it will take n^2
steps to complete the
sorting. The pseudocode of
such an algorithm is;
For i from 0 to (n-1)
nd smallest number
between numbers[I] and
numbers[n-1]
swap smallest
number with number[I]
increment i every
time
Source code:
int maxvotes = 0;
fi
fi
fi
fi
 for (int i = 0;
i < candidate_count;
i++)
{
if
(candidates[i].votes
> maxvotes)
{
maxvotes
=
candidates[i].votes;
}
}
Bubble sort;
In this algorithm, the control
compares a pair of items in
each iteration. It iterates till
the 2nd last item of the
string. When it stars, it
fi
compares a pair of items in
each iteration. It iterates till
the 2nd last item of the
string. When it stars, it
checks the rst 2 items. The
smaller number is swapped
to left while greater
continues. It then
compressed it with next
item, the smallest is again
shifted to left and greater
continues. It compare it with
each element till it goes to
n-2 element. There it
compare it with the last
element and the greatest
element is shifted to
rightmost side. It repeats
this process again and
again until all the items are
fi
element is shifted to
rightmost side. It repeats
this process again and
again until all the items are
sorted. In this algorithm, it
focus more on shifting the
greater item on right side.
Hence, it ignores the last
element every time as it is
already sorted(the greatest
item is shifted to end). So it
ignores the last swapped
element to the end and
iterates over other
remaining pairs. Generally
speaking, this is not very
fast either. Its running time
for upper bound is O(n^2)
but the only optimisation
here is the its running time
fi
fast either. Its running time
for upper bound is O(n^2)
but the only optimisation
here is the its running time
for lower bound is Ω(n).
Thats too if we give it a
condition that if it does not
make any swap, terminate
the program. If we do not do
that, it will just blindly iterate
over the whole process
even if the data is already
sorted. The pseudocode of
such an algorithm is;
Repeat (n-1) times
for i from 0 to (n-2)
if numbers[i] and
numbers[i+1] are out of
order
fi
 if numbers[i] and
numbers[i+1] are out of
order
swap them
increment I every
time
if no swaps
quit
In a more broader sight,
both these sorting
algorithms take same
running time and are hence
slow. But there are better
algorithms!
Recursion:
In a vague way, a function
is recursive if it calls itself.
But thats really dont explain
recursion in an easy way.
Albeit, recession is actually
fifi
fi
 is recursive if it calls itself.
But thats really dont explain
recursion in an easy way.
Albeit, recession is actually
a function calling itself
inside of itself. But to
understand properly, let’s
take a different approach.
The approach we are going
to take is actually more
closer to iteration.
Sometimes, we have larger
problems in our code that
cant be solved all at once.
So we need to use some
technique, some algorithm,
some function to shrink the
problem, to make it smaller.
Now, the problem is
shrinked but not solved. So
fifi
fi
 some function to shrink the
problem, to make it smaller.
Now, the problem is
shrinked but not solved. So
we use the same technique
or function to nibble it down
further. We keep using that
technique again and again
and keep shrinking the size
of the problem until it
reaches the bottom. This is
where the problem is so
shrinked that it cant get any
smaller. Now it must give us
an answer. This is where
we have reached the base
case. And when we were
doing the same technique
again and again to shrink
the problem, we were doing
fifi
fi
 case. And when we were
doing the same technique
again and again to shrink
the problem, we were doing
recursion and those were
recursive cases. Recursion
is just using the same
function on a same problem
again and again to shrink its
size. It is a very useful
technique in which the
function calls itself(used
again and again on same
problem) for solving
problems by breaking them
down into smaller, similar
problems. And the point
where it cant get any
smaller further, that is what
base case is. The case
fifi
fi
 problems. And the point
where it cant get any
smaller further, that is what
base case is. The case
where we reach the bottom
of any problem by shrinking
it again and again and now
it must give us an answer.
Using recursion is good but
it is a slower technique as it
uses the same algorithm
again and again on the
same problem and also, it is
intricate. But some
problems cant just be
solved without nibbling
them down into smaller
problems and then nally
getting an output. A function
is recursive only if the same
fifi
fi
 them down into smaller
problems and then nally
getting an output. A function
is recursive only if the same
function is being applied on
the same problem. If
function or problem(any of
them) is different, the case
is not recursive. Binary
search is an example of
recursion. We use the same
technique of searching on
left or right of middle term
again and again until we
reach the base case that is,
either we are out of terms
and it will return false or we
have found the term and
true is returned. Anyways,
we can literally call a
fifi
fi
 and it will return false or we
have found the term and
true is returned. Anyways,
we can literally call a
function inside itself. i.e. it
will do the same process
inside its own self what its
own function is. It’s kind of
iteration thing but not very
similar. In iteration, we just
have to implement any loop
construct once and it will
keep executing again and
again intuitively. However,
in recursion, we have to
write the code or any
technique manually to
actually get the compiler to
execute it again and again.
We can repeat the same
fifi
fi
 technique manually to
actually get the compiler to
execute it again and again.
We can repeat the same
code again and again or we
can call a function inside of
its own function(like while
de ning a function, we call it
inside of that) or another
recursion technique.
Recursion actually is a
function calling itself inside
of its own self. Other things
like repeating the same
code on same problem
again and gain can be
called recursion but by
de nition, recursion is when
a function calls itself inside
of it. The former examples
fi
fi
fi
 called recursion but by
de nition, recursion is when
a function calls itself inside
of it. The former examples
are more closer to iteration
then to recursion but they
are just easy to swallow the
concept of recursion.
Following is an example of
iteration and recursion for
better distinguishment,
Iteration;
{
for (int i = 0;
i < n; i++)
{
for (int j =
0; j < i+1; j++)
fi
fi
fi
 {

printf("#");
}

printf("\n");
}

}
Recursion;
void draw(int n)
{
if (n <= 0)
{
return;
}
 draw(n - 1);

for (int i = 0;
i < n; i++)
{
printf("#");

}
printf("\n");
}
Draw function is repeating
the same process inside of
it again. Our rst if
statement is acting as a
base case in this function.
We must give a base case
while using recursion
otherwise it won’t work
fi
base case in this function.
We must give a base case
while using recursion
otherwise it won’t work
properly. Another thing is
we must make an algorithm
to reach base case. Like in
this case we did n-1.
Without this, it would have
not worked properly. So we
must give base case, and
an algorithm to reach that
base case. When a function
is called inside of itself, it
executes itself again from
the start and keep repeating
the process until we reach
the base case. Another
easy implementation is;
fi
the process until we reach
the base case. Another
easy implementation is;
void draw(int n)
{
if (n <= 0)
{
return;
}

for (int i = 0;
i < n; i++)
{
printf("#");
}
printf("\n");
draw(n - 1);

}
fi
In this code, a downward
pyramid is drawn;
#####
####
###
##
#
Here, rst the for loop is
executed and and printed a
row of 5 hashes. Then it
went to new line. Finally,
draw(4) is executed inside
of itself(n - 1). The same
process is repeated again
but with 4 hashes row. Then
draw(3) is executed again
inside of itself. It keep doing
the same until it reached 0
fi
fl
but with 4 hashes row. Then
draw(3) is executed again
inside of itself. It keep doing
the same until it reached 0
which is the base case, so it
is returned and terminated.
This way, we didnt had to
use loops and super uous
code. We just executed the
same function inside of it
with a decrement of 1,
which gave us a perfect
downward pyramid.
void draw(int n)
{
if (n <= 0)
{
return;
fi
fl
 }

draw(n - 1);

for (int i = 0;
i < n; i++)
{
printf("#");

}
printf("\n");
}
Lets breakdown our
problem one by one;
First of all, suppose we get
the value of n, initially, as 5.
It will take 5 and go to rst if
statement and check for
5<=0. As it is false, it will
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 the value of n, initially, as 5.
It will take 5 and go to rst if
statement and check for
5<=0. As it is false, it will
not return anything and go
ahead. Then it will
encounter draw(n - 1 = 4)
So now, n is 4 but it does
not have any return value
for draw(4). So it will go
back and execute draw(4).
Remember, draw(5) is still
waiting for an answer in
memory, it is not vanished.
Draw(4) will go to if
statement and as it is false,
it will move ahead. No
return value for draw(4)
either, yet. It will encounter
draw(3) ahead(n(4)-1). It
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 it will move ahead. No
return value for draw(4)
either, yet. It will encounter
draw(3) ahead(n(4)-1). It
will execute the same draw
function moving back to
start of the function and
checking for if statement.
As 3 > 0, it will move ahead
without any return value. It
will then encounter draw(2)
and prepare to execute the
same function for it as well.
Remember, draw(5),
draw(4) ad draw(3), all are
stored inside of memory
waiting to complete their
execution as they had not
reached the end before the
next call was encountered.
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 waiting to complete their
execution as they had not
reached the end before the
next call was encountered.
Draw(2) will repeat the
same process and
eventually encounter
draw(1). Draw(1) will
execute now and encounter
draw(0) nally. All previous
function calls were not
completely executed and
hence waiting for
completion in memory.
Draw(0) will go back to start
and check the if statement.
As 0 = 0, hence it will
encounter a return
statement now. Return
statement tells any user-
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 As 0 = 0, hence it will
encounter a return
statement now. Return
statement tells any user-
de ned function to take that
value(or nothing, if nothing
is written with return), and
give it back to function call
to output it and end that
function at that moment. So
when a function encounter
return statement, it is
terminated right at that
moment no matter how
many lines of code are left
and it return that value(as
answer or simply nothing if
only return statement is
used without any value with
it)to where its function is
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 answer or simply nothing if
only return statement is
used without any value with
it)to where its function is
called(like literally, it
transfers the control to that
line where its function is
called). If there is nothing
written with return, it
terminates the function at
that very moment
irrespective of how many
lines of code are left in that
function and simply
transfers the control to the
line where function is called
and hence the lines ahead
of that function call are
executed wherever function
call is used. However, if
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 and hence the lines ahead
of that function call are
executed wherever function
call is used. However, if
there is any value with
return statement, then it is
terminated at that very
moment and it transfers the
control as well as that
value(which is written with
return)back to where hat
function is called. So if that
function is called inside of a
variable, the value is
transferred and stored in
that variable and control
moves ahead of that
variable. So a return
statement, rst of all,
terminates the function at
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 moves ahead of that
variable. So a return
statement, rst of all,
terminates the function at
that very moment where it is
used, and then if there is no
value along with return
statement, it just transfers
the control back the where
that function is called(and
lines ahead of the function
call are executed) but if
there is a value along with
return statement, then it
transfers that value as well
along with control back to
function call. So a return
statement terminates the
function, and transfer the
control back to where that
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 function call. So a return
statement terminates the
function, and transfer the
control back to where that
function is called. A mere
return function just returns
the control back so that rest
of the code(ahead of
function call) is executed.
As draw(0) has
encountered return, it will
terminate the remaining
code of that function and
simply transfer the control
back to where it was called.
Now, draw(0) was called
just before the for loop
where we had to print a row
for n number of #s. It gets
ahead of that function call
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 just before the for loop
where we had to print a row
for n number of #s. It gets
ahead of that function call
nally, but notice, our n at
that point, is 1. Because it
became 0 in that very
function call when we did 1
- 0,remember draw(n - 1) so
n was actually 1. Hence it
will print only 1 # in rst row.
Finally, a new line and our
draw(1) is also executed
successfully. Draw(1) is
executed with 1 # in rst
row. As we said earlier,
when a function reaches to
its end, it is automatically
returned back to its function
call. If it has any value, it
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 when a function reaches to
its end, it is automatically
returned back to its function
call. If it has any value, it
also returns that value.
Otherwise, only the control
is transferred back. Now
remember, our function
draw(1), was actually called
inside of draw(2), remember
draw(n - 1) so n was
actually 2. Finally, draw(2)
is moving ahead with value
of n as 2. It will encounter
the same loop which prints
the #s for n number of times
in a row. As n is 2 this time,
it will print 2 #s in a row and
as 1 # is already printed
due to draw(1) so we have
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 in a row. As n is 2 this time,
it will print 2 #s in a row and
as 1 # is already printed
due to draw(1) so we have
now 2 back to back rows
with 1 # at rst and 2 at
second. Draw(2) has
reached its end, so it will
transfer the control back to
where it was called.
Interestingly, it called inside
draw(3) where n was
actually 3. Hence it will
move ahead of its function
call and encounter a loop
which prints n number of #s
in a row and as n is 3 this
time, it will print 3 #s in a
row, third row actually
because draw(1) and
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 in a row and as n is 3 this
time, it will print 3 #s in a
row, third row actually
because draw(1) and
draw(2) were already
executed before. Finally,
draw(3) has reached its end
so it transfers the control
back to where it was called
and interestingly again, it
was called inside of draw(4)
where n was 4. So now a
row of 4 #s is printed ahead
of previous 3 rows. Draw(4)
has also reached end,
hence it automatically do
what return statement
would do(even if return
statement is not used but
the function has reached its
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 what return statement
would do(even if return
statement is not used but
the function has reached its
end, it will act as what
return statement would do,
transfer the control back to
where it was called).
Control is transferred to
where it was called and that
is nally, inside of draw(5)
where n is 5. Finally, a 5th
row of 5 #s is printed and
we have a pyramid of height
5. As draw(5) has also
reached its end, it will
transfer the control back to
where it was called which is
now, inside of main
function. So nally we have
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 transfer the control back to
where it was called which is
now, inside of main
function. So nally we have
our pyramid using
recursion.
-Initially, when the control
has not entered a
function(where it is called)
yet, it does not have
permission to pass ahead it,
ignoring it. It must go into it
once. Once it has entered
into a function, then upon
returning(if the function has
reached its end or it
encountered a return
statement) it can go ahead
of that function call, infact, it
will go ahead now and
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
 encountered a return
statement) it can go ahead
of that function call, infact, it
will go ahead now and
execute the rest of the code
after that function call. So
without checking any
function, control cant pass
over it without entering it.
But after it has checked
it(went inside), then it will
return eventually to where
function was called and
pass over that line.
Merge sort:
This is another sorting
algorithm but faster and
ef cient then previous ones.
It uses recursion for its
operations. In this
fi
 algorithm but faster and
ef cient then previous ones.
It uses recursion for its
operations. In this
algorithm, we use divide
and conquer strategy. It
continuously cuts down a
list into multiple sublists
until each has only one item
and then put those sublists
back but by merging them
in a correct order, thus
sorting the whole list. We
divide the list in two halves.
Then for each divided
halve, we divide them again
in two halves each thus
using recursion. We keep
repeating the same process
until we reach the base
fi
 in two halves each thus
using recursion. We keep
repeating the same process
until we reach the base
case which is we just have
one element left in each list.
Then we start the process
of merging. We compare
the divided halves, which
we have eventually, only
one element each. We
merge them in oder then we
compare the other list of
one element. We merge it.
Then these two merged lists
of two elements each are
compared and merged. We
keep repeating the same
process with each half that
we divided until we have
fi
 compared and merged. We
keep repeating the same
process with each half that
we divided until we have
our original list sorted
completely. It uses
immense recursion. We sort
the elements while
comparing after dividing
completely. It’s like we
divide them to last limit(one
element each), then we
ascend back by merging
each with each other until
we reaches the very start
from where we started. We
must divide our list in equal
halves and keep dividing
those halves again and
again until we reach the
fi
 must divide our list in equal
halves and keep dividing
those halves again and
again until we reach the
lists having one element
each only. Then we should
ascend back and start
merging the halves from
very last pair of elements,
ascending back, merging
them. We have to compare
the pairs with each other
which we divided earlier
and merge them. Finally,
we will have a fully sorted
original list just by dividing
and putting back the
elements but while merging
as well. Its pseudocode is,
fi
 and putting back the
elements but while merging
as well. Its pseudocode is,
If only one or less then
one number
Quit
Else
Search left half of
numbers
Search right half of
number
Merge them
Now, by just seeing this
code, we cant comprehend
what’s actually happening.
But what’s actually
happening is recursion
inside of rst two lines of
code. We are repeating the
same code in those two
fi
fi
fi
happening is recursion
inside of rst two lines of
code. We are repeating the
same code in those two
lines again and again until
we reach the base
case(which is a nal pair of
lists with one element
each). Its more detailed
pseudocode would be,
If only one or less then
one number
Quit
Else
Search left half of
numbers
Search left half of
numbers
fi
fi
 Search right half of
numbers
Merge them
Search right half of
numbers
Search left half of
numbers
Search right half of
numbers
Merge them
Merge them
This would be a more
detailed pseudocode and
even inn these recursive
cases, there are more
recursive cases similar to
themselves. So in each
search right half code, we
cases, there are more
recursive cases similar to
themselves. So in each
search right half code, we
are again repeating the
original 3 lines of code
again. All of the algorithm
pivot around those 3 lines.
It’s just we have to use
them recursively. Even
more detailed pseudocode
would be,
If only one or less then
one number
Quit
Else
Search left half of
numbers
 Search left half of
numbers
Search left half of
numbers
Search right half of
numbers
Merge them
Search right half of
numbers
Search left half of
numbers
Search right half of
numbers
Merge them
Merge them
Search right half of
numbers
 Search right half of
numbers
Search left half of
numbers
Search left half of
numbers
Search right half of
numbers
Merge them
Search right half of
numbers
Search left half of
numbers
Search right half of
numbers
Merge them
Merge them
 Merge them
Here, we can see more in
detail that how, by only
dividing and putting the
elements back, we can sort
a whole list. We just have to
do little comparing while
putting them back. This
algorithm is very ef cient
and swift but a little intricate
to implement because we
have to use recursion again
and again. The code is very
inclusive as it uses only 3
main lines of code and
whole sorting procedure
pivot around them. Its
running time is Θ(nlogn).
fi
main lines of code and
whole sorting procedure
pivot around them. Its
running time is Θ(nlogn).
Its upper bound and lower
bound, both are same. Its
upper bound is faster than
both, the selection sort and
the bubble sort. However,
its lower bound would only
be faster than selection sort
and slower than bubble sort
because lower bound of
bubble sort is Ω(n) while its
lower bound is Ω(nlogn)
which is slower than Ω(n).
Hence, in terms of upper
bound, our fastest algorithm
is merge sort and in terms
of lower bound, fastest is
fi
 Hence, in terms of upper
bound, our fastest algorithm
is merge sort and in terms
of lower bound, fastest is
bubble sort. Selection sort
is slower than both or them
in both bounds. However, in
upper bound, bubble and
selection sort are almost
similar.
- To identify sorting
algorithms(from above 3),
check for the upper bound
rst(unsorted lists),
algorithm that runs fastest
on such lists is merge sort.
Then check for lower
bound(sorted lists),
algorithm that runs fastest
on such lists is bubble sort.
fi
fi
 Then check for lower
bound(sorted lists),
algorithm that runs fastest
on such lists is bubble sort.
Finally, our only left option
would be selection sort. So
the remaining algorithm is
obviously selection sort.
Break statement:
It is used to break out of
any loop. It is almost always
used inside of an if-else
statement, inside of a loop
and it breaks out of that
loop. So, inside of a loop,
we use an if-else statement
to make a condition to
break the loop. Inside of
that conditional statement,
we use break statement. So
fi
fi
to make a condition to
break the loop. Inside of
that conditional statement,
we use break statement. So
if that condition is met while
executing, control enters
that if-else statement and
executes the break
statement. Hence, coming
out of that loop right from
that point and ignoring the
rest of the code. It is like the
return statement, but
speci cally for loops. Its
syntax is simple;
break;
We must use it inside of a
conditional to give any
condition for breaking.
However, we can use the
fi
We must use it inside of a
conditional to give any
condition for breaking.
However, we can use the
break statement without any
condition as well, directly
inside of a loop. If a break
statement is used inside of
a nested loop, it just breaks
out of that nested loop, not
from outer loop. So a break
statement is just used for
the loop it is inside of which,
not for its outer loops.
-If we want to nd
something maximum or
minimum we can use this
code;
fi
int maxvotes = 0;
for (int i = 0;
i < candidate_count;
i++)
{
if
(candidates[i].votes
> maxvotes)
{
maxvotes
=
candidates[i].votes;
}
}Problem Set 3:
For minimum, just change
the sign and initial value.
Problem 2(Plurality);
// Update vote
totals given a new
vote
bool vote(string
name)
{
for (int i = 0;
i < candidate_count;
i++)
{
if
(strcmp(name,
candidates[i].name)
== 0)
{

candidates[i].votes+
+;
candidates[i].votes+
+;
return
true;
}
}
return false;
}

// Print the winner

(or winners) of the
election
void
print_winner(void)
{
int maxvotes =
0;
for (int i = 0;
i < candidate_count;
i++)
 for (int i = 0;
i < candidate_count;
i++)
{
if
(candidates[i].votes
> maxvotes)
{
maxvotes
=
candidates[i].votes;
}
}
for (int j = 0;
j < candidate_count;
j++)
{
if
(candidates[j].votes
== maxvotes)
 if
(candidates[j].votes
== maxvotes)
{

printf("%s\n",
candidates[j].name);
}
}
return;
}
Problem 3(Runoff);
#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9

// preferences[i][j] is jth preference

for voter i
int preferences[MAX_VOTERS]
[MAX_CANDIDATES];
int preferences[MAX_VOTERS]
[MAX_CANDIDATES];

// Candidates have name, vote count,

eliminated status
typedef struct
{
string name;
int votes;
bool eliminated;
} candidate;

// Array of candidates
candidate candidates[MAX_CANDIDATES];

// Numbers of voters and candidates

int voter_count;
int candidate_count;

// Function prototypes
bool vote(int voter, int rank, string
name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);

int main(int argc, string argv[])

{
// Check for invalid usage
if (argc < 2)
{
printf("Usage: runoff
[candidate ...]\n");
 printf("Usage: runoff
[candidate ...]\n");
return 1;
}

// Populate array of candidates

candidate_count = argc - 1;
if (candidate_count > MAX_CANDIDATES)
{
printf("Maximum number of
candidates is %i\n", MAX_CANDIDATES);
return 2;
}
for (int i = 0; i < candidate_count;
i++)
{
candidates[i].name = argv[i + 1];
candidates[i].votes = 0;
candidates[i].eliminated = false;
}

voter_count = get_int("Number of
voters: ");
if (voter_count > MAX_VOTERS)
{
printf("Maximum number of voters
is %i\n", MAX_VOTERS);
return 3;
}

// Keep querying for votes

for (int i = 0; i < voter_count; i++)
{
 // Query for each rank
for (int j = 0; j <
candidate_count; j++)
{
string name =
get_string("Rank %i: ", j + 1);

// Record vote, unless it's

invalid
if (!vote(i, j, name))
{
printf("Invalid vote.
\n");
return 4;
}
}

printf("\n");
}

// Keep holding runoffs until winner

exists
while (true)
{
// Calculate votes given
remaining candidates
tabulate();

// Check if election has been won

bool won = print_winner();
if (won)
{
break;
 }

// Eliminate last-place
candidates
int min = find_min();
bool tie = is_tie(min);

// If tie, everyone wins

if (tie)
{
for (int i = 0; i <
candidate_count; i++)
{
if (!
candidates[i].eliminated)
{
printf("%s\n",
candidates[i].name);
}
}
break;
}

// Eliminate anyone with minimum

number of votes
eliminate(min);

// Reset vote counts back to zero

for (int i = 0; i <
candidate_count; i++)
{
candidates[i].votes = 0;
}
 }
return 0;
}

// Record preference if vote is valid

bool vote(int voter, int rank, string
name)
{
for (int i = 0; i < candidate_count;
i++)
{
if (strcmp(name,
candidates[i].name) == 0)
{
preferences[voter][rank] = i;
return true;
}
}
return false;
}

// Tabulate votes for non-eliminated

candidates
void tabulate(void)
{
for (int i = 0; i < voter_count; i++)
{
for (int j = 0; j <
candidate_count; j++)
{
if (candidates[preferences[i]
[j]].eliminated == false)
{
 candidates[preferences[i]
[j]].votes++;
break;
}
}
}
return;
}

// Print the winner of the election, if

there is one
bool print_winner(void)
{
for (int i = 0; i < candidate_count;
i++)
{
if (candidates[i].votes >
voter_count / 2)
{
printf("%s\n",
candidates[i].name);
return true;
}
}
return false;
}

// Return the minimum number of votes any

remaining candidate has
int find_min(void)
{
int minvotes = voter_count;
for (int i = 0; i < candidate_count;
i++)
 for (int i = 0; i < candidate_count;
i++)
{
if ((candidates[i].eliminated ==
false) && (candidates[i].votes <
minvotes))
{
minvotes =
candidates[i].votes;
}
}
return minvotes;
}

// Return true if the election is tied

between all candidates, false otherwise
bool is_tie(int min)
{
for (int i = 0; i < candidate_count;
i++)
{
if ((candidates[i].eliminated ==
false) && (candidates[i].votes != min))
{
return false;
}
}
return true;
}

// Eliminate the candidate (or

candidates) in last place
void eliminate(int min)
{
 for (int i = 0; i < candidate_count;
i++)
{
if ((candidates[i].eliminated ==
false) && (candidates[i].votes == min))
{
candidates[i].eliminated =
true;
}
}
return;
}