CS6601 Midterm – Spring 2020
Please read the following instructions thoroughly.
Fill out this PDF form and submit it on Gradescope and then on Canvas for backup purposes.
You have unlimited resubmissions until the deadline. You can: (a) type directly into the form – we highly recommend using Adobe Reader DC (or Master PDF on Linux). Other programs may not save your answers, so please keep a backup; or (b) print, hand-write & scan. You can combine the methods as well.
Submit only a single PDF – no phone pictures, please! (You may use an app like CamScanner or Office Lens if you do not have scanner access.) Do not add pages unless absolutely necessary; if you do, please add them at the end of the exam only, and clearly label both the extra page and the original question page. Submit ALL pages of the exam, not only the completed ones.
Do not forget to fill the checklist at the end before turning in the exam. The exam may not be graded if it is left blank.
The exam is open-book, open-note, open video lectures, with no time limit aside from the open period. No internet use is allowed, except for e-text versions of the textbook, this semester’s CS6601 course materials, Piazza, and any links provided in the PDF itself. No resources outside this semester’s 6601 class should be used. There is no collaboration on the exams. Do not discuss the exam on Piazza, Slack, or any other form of communication. If there is a question for the teaching staff, please make it private on Piazza and tag it as Midterm Exam with the question number in the subject line (for example, a question on Search would be “Midterm Exam #2 Search”).
Please round all your final answers to 6 decimal places, don’t round intermediate results. You can use round(your_number, 6) function in Python for help.
You will not receive full credit if your answers are not given to the specified precision.
Point breakdown (Each question has sub-parts with varying points):
Q1 Q2 Q3 Q4 Q5 Q6 Q7 Total
Pts 8 12 16 16 16 16 16 100
1. Game Playing (8 points)
Question A.
(2 points)
Solve the game tree using alpha-beta pruning. The algorithm evaluates the branches from left to right. Indicate which branches are pruned by checking the correct box. Show the value of each node.
When you prune a branch at a top-level, check all the sub boxes/branches down along that path as well. If an upper-level node in a branch gets pruned and you’ve selected the checkbox to indicate that it is pruned, you DO need to fill in values for the “unvisited” underlying nodes and should also check all the boxes to indicate which branches are pruned.
Make sure to use inequality signs if appropriate.
Page 2 out of 46
Question B.
(3 points)
Reorder the leaf nodes of the tree from Question A to maximize the number of branches that are pruned. In other words, for the game represented by the tree in Question A, what would the best possible node ordering for Alpha-Beta if the algorithm operates from left to right?
When you prune a branch at a top-level, check all the sub boxes/branches down along that path as well. If an upper-level node in a branch gets pruned and you’ve selected the checkbox to indicate that it is pruned, you DO need to fill in values for the “unvisited” underlying nodes and should also check all the boxes to indicate which branches are pruned.
Make sure to use inequality signs if appropriate.
B.1. What is the total number of pruned branches? _________________________________________________
Page 3 out of 46
Question C.
(3 points)
Reorder the leaf nodes of the tree from Question A to minimize the number of branches that are pruned. In other words, for the game represented by the tree in Question A, what would the worst possible node ordering for Alpha-Beta if the algorithm operates from left to right?
When you prune a branch at a top-level, check all the sub boxes/branches down along that path as well. If an upper-level node in a branch gets pruned and you’ve selected the checkbox to indicate that it is pruned, you DO need to fill in values for the “unvisited” underlying nodes and should also check all the boxes to indicate which branches are pruned.
Make sure to use inequality signs if appropriate.
C.1. What is the total number of pruned branches? _________________________________________________
Page 4 out of 46
程序代写 CS代考 加QQ: 749389476
2. Search (12 points)
Traditional search algorithms such as Uniform Cost Search and A* are commonly applied to problem spaces surrounding physical space, but there are many other fields that can take advantage of these algorithms. One such space is the area of optimizing activity in the global currency exchange market. If a particular investor wanted to convert her wealth from the US Dollar to Japanese Yen, it may be more financially beneficial to first exchange their dollars to an intermediary currency, and then exchange that currency to Yen rather than exchange their USD to Yen in one initial exchange. If the state of the current currency exchange market in one moment can be modeled as a graph, then shortest-path algorithms work very successfully to solve this problem. Read the scenario below and work through the following problems to see such an example:
In the distant future, Maks is a middle-class citizen of Isbelland: the nation governed by the powerful political head Charles Isbell. He is a particularly clever investor in the global financial market and has received a tip from a trusted source that the currency of Isbelland, the Isbellion (ISBL), will crash in value over the next couple years. To protect his financial future, he wants to convert his wealth from Isbellions to a much more stable currency that has a stronger future. After sufficient research, he has determined that the currency with the most promising future is the Starner Buck (STNR), the currency of the economic powerhouse Starneria. Isbelland and Starneria have very tense relations, however, and the national governments have imposed a large tax to convert currencies between them. The two nations have a web of political relationships, however, and Maks sees he can utilize intermediary currencies of foreign countries to avoid this tax. He must utilize a combination of currency transfers to transfer his wealth to Starner Bucks, and he realizes this is a problem that he can apply classical search algorithms to.
Page 5 out of 46
Firstly, he models the current political and economic landscape as a graph structure, resulting in the following:
Figure 1.1: Currency Graph
Each node represents a national currency, and each graph edge represents the loss in total value when exchanging wealth between currencies. For example, if Maks was exchanging $100 Australian Dollars (AUD) to Turkish Lira (TRY), the overall value would be reduced by a
Page 6 out of 46
factor of .0621 due to transactional costs and he would end up with an amount of Turkish Lira that’s actually worth $93.79 AUD.
a. If Maks has a starting value of 10,000 Isbellions and wants to convert all his wealth to Starner Bucks, what’s the optimal order of currency exchanges he should perform to lose the least amount of money? Enter your answer as a comma-separated list using the node labels in the graph above. (3 points)
______________________________________________________________________ b. What is his final value of Starner Bucks when evaluated in Isbellions? (1 point) ______________________________________________________________________
Page 7 out of 46
After performing all his exchanges, Maks is reassured that his wealth is protected despite the falling value of the Isbellion. He becomes slightly curious about his source of information and decides to look further as to the reasons behind the predicted currency devaluation. After researching the topic in-depth, Maks comes to the realization that Isbelland is on the verge of completely failing as a state and descending into anarchy due to gross mismanagement. Wanting to avoid the fallout of this catastrophe, he wants to travel to Starneria and become a citizen as soon as possible. He no longer cares about the financial cost and wants to relocate in the fastest manner possible. Luckily, Isbelland and Starneria are connected by landmass and Maks owns a car. See the information below and answer the following questions about the A* algorithm:
Figure 1.2: Distance Graph
Page 8 out of 46
For the sake of simplicity, imagine that Maks never needs to refill his gas tank and travels at a constant speed. Additionally, each geographical location will be represented by a simple (X, Y) coordinate pair. See these coordinates in the table below:
Isbelland Pandel Thrunway Joyneria Norvigden Howardan Littmania Bobickstan Essastan Serbankia Balchea Starneria
220.2 154.5 360.4 248.3 148.7
63.2 111.3 182.9 206.0 365.3 246.4
382.1 350.4 323.2 287.1 240.5 300.5 211.7 132.6
92.0 178.6 185.6
Using the Euclidean distance function as a heuristic, the questions is:
49.3 cost of a node in the below
f(x) = g(x) + h(x)
c. What is the total cost of the node ‘Serbankia’ when it is added to the frontier? (2 points)
______________________________________________________________________
Page 9 out of 46
程序代写 CS代考 加微信: cstutorcs
d. What is the total cost of the node ‘Serbankia’ immediately before it is popped from the frontier? (2 points)
______________________________________________________________________
e. When performing our A* search we find that the node ‘Essastan’ is expanded, and we see our goal, Starneria, in its neighbors. Given that our Euclidean distance function is an admissible heuristic, can we terminate the search immediately upon finding our goal node in this scenario? (1 point)
● Yes ● No
Provide some brief reasoning to your answer:
INCLUDE INPUT BOX
f. Taking d(x) to be the value of the Euclidean distance heuristic above, which of the following heuristic values are also admissible in the above graph? Select all that apply. (3 points)
○ h(x)=2*d(x)
○ h(x) = log2(d(x))
○ h(x) = d(x) + 100
○ h(x) = d(x) − 100
○ h(x)=1*d(x) 2
Page 10 out of 46
Code Help
3. Optimization Algorithms (16 points)
Section A.
(9 points)
Genetic algorithms are a unique class of optimization processes popularized by John Holland, a prominent computer scientist who modeled optimization algorithms under the naturally occurring processes of natural selection. Like the name suggests, genetic algorithms utilize the mechanisms found in genetic evolution and apply them to various problem spaces to ‘evolve’ solutions into even more optimal solutions.
In their search, genetic algorithms process a population of chromosomes (potential solutions), which represents the search space solution, with three operators — selection, crossover, and mutation. The population of individuals go through a sequence of unary (mutation) and higher-order (crossover) transformations. These individuals strive for survival; a selection scheme, biased toward fitter individuals, selects the surviving generations. After some number of generations, the program converges, and the best individual hopefully represents the optimal solution.
Genetic algorithms have had significant success in many modern domains such as encryption, power flow optimization, music composition, and many more. In this section, you’ll apply genetic algorithms to a Civil Engineering problem for the design of water distribution systems.
Background:
During the election to her office, the current Mayor of Starneria had promised to revamp the old water pipeline in her city. After assuming office, she learns from her advisors how Genetic Algorithms can help in devising an optimal design for the pipeline. She is challenged by the Isbelland pipe factory that if she finds the most optimal pipe design, they would forego all the operational costs for the next 100 years. Aware that you’ve learned about Genetic Algorithms in your AI class, she comes to you for help in finding the most optimal network. You start off by trying to understand the problem formulation.
Page 11 out of 46
Problem Formulation:
As you can see on the next page, there’s a sample pipeline network. There are 4 nodes and 4 links (the pipes). The factory can only produce pipes with diameters of size (in inches) from the set T = {12, 16, 20, 24}. Your objective is to find the diameters from the available set for all the links at the minimum possible cost.
An individual ‘D’ in the population is represented by the set of diameter values for the pipes. The diameter values are arranged in alphabetical order starting with diameter of pipe AB, BC until the last edge.
For example, for Figure 3.1 (next page), it would be {AB, BC, CD, DB}. Fitness Function:
In the genetic algorithms population, there are some individuals who are ‘fitter’ than others. To quantify this fitness characteristic, genetic algorithms use what is called a fitness function to compare specimens. This function is dependent upon the problem the algorithm is trying to solve, and computes the value we’re trying to maximize.
For this particular problem, we’ll take advantage of the easily computable cost of the pipeline network. The cost of the network consists of two components – the manufacturing cost of the network and the installation costs. The factory has put out its manufacturing costs for different pipe diameters varying on the length. The manufacturing cost fCost is given as:
fCost =1.1×L ×D1.5
where L is the length of the pipe and D is the diameter in inches and fCost i s the cost in dollars
Thus the manufacturing cost of the network(D) consisting of N pipes becomes
fCost(D) = 1.1×ΣNj LjDj1.5
Page 12 out of 46
Another aspect to this water distribution problem is the installation cost to handle the water pressure constraints in the network. This term is given by:
γ(D) =10000×ΣjN(Lj0.5/Dj2.5) And thus, the total cost is given by:
C(D) = fCost(D) + γ(D)
Figure 3.1 : A sample pipeline network
For an individual S = {16, 20, 12, 24},
fCost(S) = 1.1×(5×161.5 +7×201.5 +9×121.5 +8×241.5) = 2486.908676
γ(S) = 10000 × ( 50.5 + 70.5 + 90.5 + 80.5 ) = 106.790896 162.5 202.5 122.5 242.5
C(S) = fCost(S) + γ(S) = 2593.699572 Fitness Function = 1 = 0.000386
Now since we want to minimize the cost of the pipeline, we would like a smaller cost network to be more fit than a larger cost one. To account for this, our fitness function for this individual
Page 13 out of 46
would be 1 , the inverse of the cost. You can see the calculations for the sample network in C(D)
accordance with the network in Figure 3.1.
Now you are given the below pipeline network as shown in Figure 3.2 for Starneria.
Figure 3.2: Starneria Pipeline Network
Q.3.A.1 (2 points)
Based on the network provided in Figure 3.2, calculate the cost of the given four networks. Remember that the sample {12, 20, 16, 24, 12} represents the diameters for the links A-B, B-C, C-D, D-E and E-B respectively. Report your final answer according to the rounding rules of the exam. Please don’t round any intermediate value.
Hint: You may find this easier to code.
Specimen Network 1 Network 2 Network 3 Network 4
Chromosome {12, 12, 16, 20, 24} {24, 24, 12, 12, 16} {16, 20, 24, 12, 20} {24, 12, 20, 16, 16}
Fitness Score
Page 14 out of 46
Q.3.A.2 (0.5 point)
You’re given a budget of $4500 to build this pipeline.
Based on the network provided and your budget which of the following specimens would be feasible? (select all that apply)
■ Network 1
■ Network 2
■ Network 3
■ Network 4
In order to breed two specimens together to create a new generation, we first have to choose which specimens are going to function as parents. One standard approach to complete this step is called fitness-proportionate selection (also referred to as roulette wheel selection). After computing the fitness scores for each specimen in a population, we’ll normalize these scores to sum up to one. Using these normalized scores as a probability distribution, we’ll select two random parents to pass on their genetic material to the next generation.
Q.3.A.3 (2 points) Using pre-computed costs of the network for the following specimens, calculate the probability that each will be a parent of the next generation. Round your final answer according to the rounding rules of the exam.
Network 5 Network 6 Network 7 Network 8
Fitness Score
0.000316 0.000374 0.000389 0.000347
Probability to be a Parent
Page 15 out of 46
Crossover:
After choosing the specimens that will be parents, we have to apply a defined crossover function to generate children from the genetic material of the parents. Unlike the design of the fitness function, there are a number of standard approaches to crossover processes that work sufficiently. For this problem, we use the Arithmetical crossover. That is, the children generated would have genes which are a linear combination of the genes of the parents. Also, an invariant that needs to be maintained during the crossover process is that both the children need to be a valid specimen i.e. in our case, each gene should have a diameter amongst the available diameters. The design for the same is outlined below:
If there are two parents D1 = {d11, d21, d31, d41, d51} and D2 = {d12, d22, d32, d42, d52} selected for crossover, then the two offsprings J1 and J2 generated would be as follows:
Jk = {j1k, j2k, j3k, j4k, j5k} for k=1,2
where ji1 = λdi1 + (1 − λ)di2 and ji2 = (1 − λ)di1 + λdi2 and λ is a constant s.t. 0 ≤ λ ≤ 1 .
Apart from these rules, we need to do one more check to ensure the children satisfy the constraint that each diameter should belong to the set T = {12, 16, 20, 24}
● If ji1 does not belong to T, assign the greatest value in T that is less than ji1 . e.g. if you get ji1 as 14, you assign it the value 12.
● If ji2 does not belong to T, assign the smallest value in T that is greater than ji2 . e.g. if you get ji2 as 14, you assign it the value 16.
After the crossover step, the children are added to the population for the next generation.
Page 16 out of 46
Q.3.A.4 (2 points)
For two parent networks P1={16, 12, 24, 20, 12} and P2={20, 12, 16, 12, 24}, perform the crossover steps as listed above assuming the value of λ is 0.75. Mark from the below alternatives which would be children of this crossover operation. Select all that apply.
■ {16, 12, 24,
■ {20, 12, 16,
■ {16, 12, 20,
■ {17, 12, 22,
■ {19, 12, 18,
■ {20, 12, 20,
■ {12, 20, 20,
■ {16, 20, 16,
Q.3.A.5 (1 points)
20, 12} 12, 24} 16, 12} 18, 15} 14, 21} 16, 24} 24, 16} 12, 12}
With regards to Arithmetical Crossover, which of the following statements are true? Select all that apply.
■ For λ = 1 , only one new value is added to the next generation’s population.
■ For λ = 0.5 , only one new value is added to the next generation’s population.
■ For λ = 0.25 , no new values are added to the next generation’s population.
■ For λ = 0 , no new values are added to the next generation’s population.
Page 17 out of 46
In order to introduce new characteristics into a population, the crossover operation is not enough. Again similar to natural populations, we need to ‘mutate’ children in a small but potentially important manner to traverse our search space efficiently. This method allows children to have characteristics that their parents do not have, and in this way the population as a whole avoids being homogeneous.
In this algorithm, we make use of Gaussian mutation. Given network D = {d1 , d2 , ., di , .., dN } as chromosome and gene di is randomly selected for mutation, then the gene di* resulting from the application of Gaussian mutation is given by:
di* = di + 4 ×floor(N(0, σ))
And the mutated network would be D* = {d1, d2, ., di*, .., dN }
Where N(0, σ)is an independent random Gaussian number with mean zero and standard deviation σ = 0.1 × d max where dmax is the maximum value of the gene and the floor
function is the greatest integer function, basically the math.floor method in python.
If the value di* goes out of bound, you simply wrap it around i.e. to get the gene values within the limit, the gene values are adjusted by adding or subtracting multiples of range.
Q.3.A.6 (1.5 points)
Mutate the network D = {16, 16, 24, 12, 20} using the method above. Use i = 4 and assume that N (0, σ) = 1.7 . Report the new network generated D* .
_________________________________________________________
Congratulations! You’ve completed all the steps of a real-world, relevant application of genetic algorithms and hopefully understand the structure and execution of this class of optimization process. Typically this algorithm is run through many iterations until there’s no significant difference in the fitness between generations. The best specimen found at this point is returned as the final result.
Page 18 out of 46
Section B.
(7 points)
Alice’s Flexible Schedule
Alice is a grad student at Georgia Tech, and she is taking CS6601 this semester. As most of you can relate, her schedule is going crazy because of the workload of the Assignments, and she is trying to find ways to manage her time better.
Let us take a peek at Alice’s typical Saturday – the one day each week she gets some time to herself. Out of habit, she always does the following things, in the exact same order.
Please find below the things she does, and the time each thing takes assuming that there is no waiting time.
1. She brushes her teeth and grabs coffee (T)
2. She goes to the Trailblazer Gym and works out (W)
3. She gets back home and takes a shower (S)
4. She meets with a friend at Gibbs’ Cafe for brunch (G)
5. She buys groceries at A-star Supermarket (A)
6. She stops to drink bubble-sort tea (B)
Time in minutes
However, she has observed that things don’t always go as planned. Some things could take much longer, because of the waiting time. Alas, such is life!
Page 19 out of 46
Over the past few weeks, she made the following observations of the waiting time for
each task, given the time slot she
does it in.
Waiting time in minutes
6:00- 9:00
9:01- 12:00
12:01- 15:00
15:01- 18:00
18:01- 21:00
21:01- 00:00
Workout (W)
Shower (S)
Gibbs’ Cafe (G)
A-star Supermarket (A) Bubble-sort Tea (B)
(Please keep in mind that
example, if Alice tries to start working out (W) at 12:00 pm, she will first have to wait 30 mins, causing the entire task will take 90 mins – including waiting time, and so she will finish by 1:30 pm)
Alice, not wanting the things she learned in CS6601 to go to waste, now decides to make use of Simulated Annealing to find out how to minimize the waiting time throughout the course of her day. She wants to pick a time that she should start doing these tasks such that it takes the least amount of overall time to complete. In other words, she wants to do all the tasks while making sure she is left with the maximum amount of time at the end of the day.
30 60 30 60 30
0 0 0 0 30 30 0 60 30 0 0 0 0 30 0
30 60 30 120 30
90 30 90 30 0 0 30 0 60 30 60
waiting depends on the slot in which she starts the task. For
Page 20 out of 46
➢ Alice starts her next task as soon as the previous task is finished. There is no gap between two consecutive tasks
➢ All times are in 24-hour format
➢ Waiting time for any task outside this range of 6:00 am to 12:00 am can be considered
➢ Round all intermediate values to 6 digits, and use those for further computation
➢ If the probability of acceptance is greater than 1, it means that the sample is always
accepted, and so round it down to 1
➢ Total time taken = (Start time – End time), converted to hours. (Note: every half-hour is
represented as 0.5, i.e., 1 hour 30 mins would be 1.5 in this column)
➢ Energy = (Total time taken)-1
➢ Temperature = Temperature as used in Simulated Annealing
➢ You can assume that every start time is accepted
Help Alice by filling in the table on the next page. Calculate the probability of acceptance for each start time. The first and fourth entries have been filled for you.
Page 21 out of 46
Please fill in the following table (2 points):
Time Taken (hours)
Temp- erature
Probability of Acceptance
Start Time of Task
17:00 17:30
5:00 13:00 11:00
0.07 1 0.06
0.04 0.832081 0.03
Page 22 out of 46
Given that Alice starts at 9:00, answer the following questions:
Q.3.B.1.a What time does she start taking a shower? (0.5 points)
__________________________________________________ Q.3.B.1.b What time does she finish all her tasks?(0.5 points) __________________________________________________
Q.3.B.1.c How many hours did she take to do all her tasks?(0.5 points) __________________________________________________
Q.3.B.1.d What is ΔEnergy for this start time?(0.5 points) __________________________________________________
Q.3.B.1.e What is the probability of acceptance for this start time?(0.5 points) __________________________________________________
Given that Alice starts at 11:00, answer the following questions:
Q.3.B.2a What time does she finish buying groceries from A-Star Supermarket?(0.5 ps)
__________________________________________________
Q.3.B.2b What time does she finish all her tasks? (0.5 points) __________________________________________________
Q.3.B.2c How many hours did she take to do all her tasks? (0.5 points) __________________________________________________
Q.3.B.2d What is ΔEnergy for this start time? (0.5 points) __________________________________________________
Q.3.B.2e What is the probability of acceptance for this start time? (0.5 points) __________________________________________________
Page 23 out of 46
4. Constraint Satisfaction Problems (16 points)
Question A.
(9 points)
The year is 6601 A.D. and after years of conflict, including pranking and petty bickering, the nations of Starneria and Isbelland have finally settled their differences. Now that the citizens of each nation are free to travel back and forth, you, an AI-savvy entrepreneur, decide to start a travel agency that claims to craft itineraries for clients no matter their constraints. Since Isbellians have not, until now, been very familiar with the best places to visit within Starneria, there are many Isbellians that are expecting you, with all of your AI knowledge in constraint-satisfaction, to be an expert that will help them plan their awaited vacations to Starneria.
The wonderful land of Starneria is comprised of 9 regions: A, B, C, D, E, F, G, H, and I. Each region boasts its own popular sites and attractions, but not every region will be right for everyone.
Page 24 out of 46
Region A – Contains the capital of Starneria located in the north, full of museums, plays, and shopping areas
Region B – Southern region, known for being notably hot all year. It has a small stretch of coastline where much of the nation’s goods are imported at a major port.
Region C – Mountainous region in the north, popular among hikers
Region D – A coastal region in the south with its share of beaches. It is popular even among Starnarians, resulting in many shops and restaurants.
Region E – A northern region that receives a noteworthy amount of rain. Much of the nation’s crops are grown here.
Region F – A southern island with beautiful beaches and coastline that is only accessible by boat from Region B or D, as there is no domestic airport in this region.
Region G – While technically a central region, this is officially considered part of the north. Many cultural sites are present here including museums. Shopping boutiques are always nearby. Region H – Desert region in the south, with the hottest temperatures in Starneria, but also home to the largest markets in the nation. Any shopper would love visiting this region.
Region I – Home of the only international airport in the country. With its central location, it offers the best of the northern and southern cultures. Still, it is officially part of the north as it shares more in common with the other northern regions.
Note#1 – Any region can be accessed from any other region (via domestic flights) except for Region F which must be entered/exited via boat from/to Region B or Region D.
Note#2 – All tourists visiting Starneria must enter and exit via an international airport for legal reasons.
Jack, Jane, John, and Jamie come to you for help with planning their itinerary. Each member of the group has different things they want out of the trip, but each also has restrictions to work around. Each person doesn’t care where they go on the trip as long as their personal constraints are met.
Jack – Considering that Isbelland has no coastal borders, he wants to spend time by the water in at least