computer science and ANALYSIS OF ALGORITHMS
4n9r58y2u
group_2.zipgroup 2/checklist gp 2-3.pdf
CS 325 Group Project 2 checklist
Grading TA: Evgenia Chunikhina
January 15, 2016
Here we provide a checklist for group project 2.
You need to submit the following files:
� Complete source code, and a file with short instructions on how to run the code, in a single zipped file (.zip, or .gzip)
� Report as a separate pdf file (detailed description of the requirements for the report are given below)
Your report must include:
� Section 0: List all group members (please, write full names and surnames)
� Section 1: Introduction (give a short description of a problem you are solving)
� Section 2: Algorithm 1 Enumeration (Brute-force algorithm)
� Subsection 2.1: pseudocode for algorithm 1
� Subsection 2.2: short explanation of your pseudocode
� Subsection 2.3: analysis with explanation of the running time; in- clude lower bounds on the running times
� Subsection 2.4: solutions to the corresponding input instances
� Section 3: Algorithm 2 Dynamic Programming
� Subsection 3.1: pseudocode for algorithm 2
� Subsection 3.2: short explanation of your pseudocode
� Subsection 3.3: analysis with explanation of the running time; in- clude lower bounds on the running times
� Subsection 3.4: solutions to the corresponding input instances
� Section 4: Algorithm 3 Optimal Dynamic Programming (SECTION 4 IS OPTIONAL. FOR EXTRA CREDIT ONLY)
1
� Subsection 4.1: pseudocode for algorithm 3
� Subsection 4.2: short explanation of your pseudocode
� Subsection 4.3: analysis with explanation of the running time; in- clude lower bounds on the running times
� Subsection 4.4: solutions to the corresponding input instances
� Section 5: Conclusion (briefly discuss differences between proposed algo- rithms and their running times)
2
group 2/dp.txt
SAMPLE INPUT 1: 3 1 1 1 3 SAMPLE OUTPUT 1: 3 SAMPLE INPUT 2: 4 2 2 2 3 1 4 SAMPLE OUTPUT 2: 4 SAMPLE INPUT 3: 8 2 2 1 8 5 4 SAMPLE OUTPUT 3: 5 SAMPLE INPUT 4: 13 5 6 6 4 2 7 5 13 1 6 9 4 2 SAMPLE OUTPUT 4: 11 SAMPLE INPUT 5: 67 16 14 12 53 32 18 11 48 17 63 7 54 20 4 6 8 14 56 66 32 38 16 8 40 19 52 53 12 21 51 22 18 SAMPLE OUTPUT 5: 25 SAMPLE INPUT 6: 139 50 56 8 121 112 9 28 84 82 129 31 91 138 25 59 89 52 36 33 110 54 37 79 109 55 16 96 26 93 101 76 104 113 139 118 47 63 128 123 15 136 132 44 70 49 86 11 23 22 39 69 68 86 33 92 19 125 41 14 60 75 135 50 61 57 28 104 43 129 128 83 48 133 65 45 114 55 11 58 97 17 42 91 138 34 127 2 35 103 49 18 118 111 74 101 124 113 47 70 52 5 139 69 93 13 29 40 12 SAMPLE OUTPUT 6: 73 SAMPLE INPUT 7: 201 184 74 131 94 181 99 138 193 17 145 161 165 25 107 36 142 171 110 188 97 154 28 173 60 183 53 71 13 43 184 5 168 73 139 106 91 18 93 192 163 29 120 62 21 96 78 149 87 81 84 47 80 167 31 14 124 151 178 162 147 101 105 123 30 113 41 121 38 72 12 68 117 129 130 46 166 35 104 74 116 108 158 44 180 100 122 182 66 136 52 55 23 194 2 42 102 160 172 50 156 51 103 195 48 8 10 137 152 98 15 143 127 176 75 89 24 70 189 144 135 76 115 77 32 164 170 153 82 196 86 20 33 85 169 83 159 57 199 174 64 134 109 95 140 191 79 67 179 197 150 37 58 119 186 27 88 111 59 4 146 1 26 34 22 201 7 16 114 65 177 63 9 19 69 157 45 49 190 112 148 118 132 133 56 61 187 201 146 116 189 159 71 10 21 41 35 38 106 95 7 43 135 193 175 117 186 185 93 194 191 3 176 196 5 148 177 45 11 144 152 72 187 147 182 14 51 138 94 183 114 64 47 76 198 174 49 123 20 179 118 97 34 86 2 105 75 98 134 178 190 80 92 81 112 9 110 87 107 17 160 SAMPLE OUTPUT 7: 75 SAMPLE INPUT 8: 399 197 90 319 348 155 143 160 147 165 3 91 323 58 179 9 57 309 258 332 59 196 194 110 379 158 19 238 21 305 30 355 339 259 252 88 233 245 137 135 17 236 125 7 247 78 124 69 394 311 15 276 67 266 335 157 146 28 87 269 248 39 268 142 224 74 227 301 326 280 206 112 308 24 111 290 396 82 13 398 369 230 73 72 99 171 350 22 303 362 220 246 214 81 153 231 306 232 144 325 217 283 49 31 315 304 84 47 302 185 384 86 164 120 297 363 187 166 116 317 186 318 286 212 136 288 223 382 294 287 347 260 79 209 356 345 391 210 310 383 131 284 397 381 95 254 8 291 103 395 299 113 94 393 150 48 32 239 373 195 34 18 11 2 43 174 114 215 132 235 46 41 182 278 264 334 378 328 300 267 64 193 261 340 122 85 342 152 207 368 341 16 273 126 181 117 60 241 274 51 345 394 138 111 98 191 254 251 180 205 137 172 243 331 306 94 311 288 294 328 253 2 303 333 176 112 10 140 88 81 295 291 124 203 58 146 101 48 14 365 47 301 376 107 18 350 255 245 347 395 25 399 280 273 65 165 310 219 96 267 171 136 357 276 197 248 237 117 247 340 249 309 187 67 156 129 262 298 261 102 164 367 145 356 393 308 5 45 396 392 SAMPLE OUTPUT 8: 126
group 2/dp_set1.txt
Test #1: 19 9 10 5 2 18 16 9 12 17 15 6 5 19 2 6 16 14 7 17 15 9 Test #2: 14 4 14 2 6 1 12 8 2 7 14 13 5 12 10 11 4 1 3 9 6 Test #3: 10 9 7 1 5 10 4 8 2 9 3 7 7 10 6 1 2 4 8 Test #4: 16 3 14 7 14 2 16 6 15 4 13 2 1 12 10 3 8 14 9 7 Test #5: 19 5 17 14 6 13 5 4 3 10 1 13 6 14 8 17 11 5 7 12 19 4 18 16 2 Test #6: 12 6 1 4 5 8 12 10 3 10 Test #7: 18 18 15 6 10 7 18 12 14 3 11 4 1 17 2 9 15 8 5 16 13 15 2 14 3 8 6 17 1 7 11 10 5 18 9 13 Test #8: 14 12 8 14 13 11 1 3 4 7 9 8 6 2 5 8 6 2 12 9 11 7 13
group 2/dp_set2.txt
Test #1: 104 5 79 82 5 94 47 21 51 70 21 11 1 31 9 93 76 65 38 92 20 81 45 32 63 2 23 55 40 64 4 73 97 84 42 83 90 43 18 100 27 52 50 15 85 5 94 96 54 79 25 36 102 34 89 17 69 26 77 80 12 67 14 47 62 103 101 74 29 41 60 87 19 16 3 24 6 7 61 44 95 88 72 28 78 48 75 Test #2: 102 69 17 84 6 2 54 24 99 29 35 56 12 27 26 7 93 46 32 64 37 75 4 71 81 68 48 49 92 96 94 23 11 97 9 86 14 50 15 69 38 91 13 65 5 34 36 85 40 30 83 60 59 77 101 41 8 66 76 28 90 25 89 53 18 43 74 72 62 61 70 17 86 55 94 54 82 31 69 68 62 20 10 48 93 76 56 59 50 Test #3: 105 41 58 38 30 92 77 36 28 85 14 89 17 57 82 13 97 1 68 55 42 49 62 27 84 26 18 100 16 71 91 102 3 78 53 31 64 81 48 11 33 29 90 20 80 22 10 5 59 37 63 104 87 73 88 83 17 96 39 50 51 92 1 44 52 102 58 100 9 53 67 43 3 60 97 25 76 24 30 48 27 77 49 23 95 28 85 62 15 35 12 72 55 99 78 79 11 105 57 45 68 13 Test #4: 104 104 31 59 19 36 76 78 96 3 81 61 85 10 48 103 14 100 87 35 29 67 80 43 65 68 70 15 30 26 69 21 60 62 74 20 88 4 5 91 9 49 77 18 7 71 47 64 39 95 28 53 82 89 92 93 72 83 79 31 56 2 16 8 58 50 12 37 45 32 94 55 75 22 102 23 63 73 40 54 44 11 25 86 66 97 34 13 52 98 41 51 24 38 1 6 84 99 90 101 104 17 27 33 57 46 42 58 94 71 30 92 4 75 29 87 96 24 49 83 68 91 44 54 17 73 76 46 41 103 33 97 101 25 34 53 26 16 Test #5: 107 27 102 40 56 12 54 87 65 96 1 81 97 16 36 33 24 51 82 66 67 75 93 46 15 17 41 19 102 32 8 97 67 73 14 57 16 86 50 89 18 27 26 33 92 35 96 78 53 60 5 12 6 51 46 107 59 23 87 66 82 2 15 13 91 83 93 100 103 37 88 74 11 45 98 85 101 19 104 65 3 32 72 95 106 79 61 84 81 29 68 75 102 43 63 36 56 94 77 31 52 80 28 49 40 48 99 58 76 20 41 71 10 1 39 70 69 9 34 44 38 47 62 42 30 25 54 7 24 21 22 64 Test #6: 106 79 26 86 42 98 96 78 91 38 67 16 87 70 25 73 29 41 32 57 35 6 68 17 100 15 105 31 27 71 44 99 7 79 48 18 55 89 60 28 97 20 77 103 90 9 26 61 104 2 5 62 63 81 102 106 84 46 34 45 51 69 39 21 49 10 101 40 14 33 30 92 4 75 37 11 64 47 59 13 66 82 74 101 22 88 73 99 41 10 30 35 68 104 1 85 89 40 71 96 57 76 17 27 95 48 37 103 Test #7: 109 108 87 61 1 32 17 40 57 55 23 106 54 82 8 100 44 9 101 59 84 94 49 92 34 35 33 16 48 31 26 60 45 3 38 50 105 87 36 43 96 75 4 79 47 85 13 29 14 37 80 81 67 56 97 24 27 91 58 53 77 52 88 7 107 15 90 71 109 70 64 2 18 10 46 12 25 76 78 62 22 39 19 66 95 63 11 73 99 108 74 5 103 98 28 104 6 21 86 30 102 72 68 83 20 41 42 51 65 93 89 8 33 107 72 35 37 41 7 32 103 34 79 15 18 25 6 59 94 76 58 106 52 50 23 48 83 90 53 102 31 5 85 36 77 61 78 108 21 12 54 56 80 74 64 14 75 96 3 39 43 100 17 60 2 16 87 20 62 55 65 63 38 4 92 73 49 88 98 42 1 11 51 40 70 99 68 66 28 93 91 71 101 109 24 30 67 27 Test #8: 108 103 81 81 5 44 53 30 93 76 97 59 98 10 74 95 27 90 46 35 11 94 19 70 77 32 80 40 48 7 58 24 39 26 31 36 45 2 33 103 88 41 25 92 86 104 37 12 20 49 63 78 4 69 73 22 105 87 61 42 43 23 72 85 84 64 68 83 89 28 8 34 60 100 1 108 101 91 47 15 107 3 50 99 66 52 62 16 38 13 17 14 79 71 9 102 65 54 6 51 67 29 82 55 106 18 56 45 25 72 33 10 87 76 52 31 73 79 92 94 23 42 21 57 41 39 67 46 81 107 18 62 13 9 93 19 27 85 69 78 34 63 5 83 98 84 2 3 40 89 16 12 65 75 24 91 105 49 61 96 51 103 59 100 7 14 88 28 97 104 43 30 101 108 15 99 4 50 66 54 8 53 74 44 102 37 71
group 2/dp_set3.txt
Test #1: 507 20 111 271 378 392 175 439 283 302 177 277 184 278 75 73 142 339 313 127 134 490 160 211 140 325 207 170 36 264 68 433 169 452 89 172 357 400 69 93 316 376 499 354 259 414 377 309 471 263 107 383 274 108 297 335 501 2 210 466 182 333 295 158 245 157 468 505 479 440 403 262 473 242 281 279 197 113 285 85 282 82 454 34 201 139 159 62 209 50 227 138 80 154 168 437 4 304 165 45 432 42 236 418 334 136 251 348 132 491 110 148 52 346 435 212 372 397 413 214 496 302 438 415 270 208 234 41 102 502 38 37 56 425 Test #2: 506 8 315 70 200 74 248 134 481 196 480 241 309 117 436 50 505 427 7 266 200 486 296 415 98 358 326 420 222 237 297 393 390 151 160 133 126 31 279 331 268 278 227 94 104 2 250 368 52 141 4 501 481 289 72 131 134 363 221 463 350 135 213 476 39 122 229 369 175 418 101 492 173 339 488 91 112 317 25 394 45 460 5 437 400 346 406 374 71 114 76 115 305 299 198 321 146 315 478 8 249 62 130 332 169 286 102 473 179 88 288 42 149 462 132 90 12 357 252 503 109 167 264 29 434 125 154 316 119 443 85 185 280 285 259 426 184 290 232 320 502 319 283 482 336 253 118 54 391 402 480 228 220 382 195 137 14 318 376 322 291 238 408 395 312 116 46 261 338 27 140 51 413 298 162 240 244 409 10 211 150 384 245 328 15 496 355 275 371 6 281 306 301 424 497 421 352 260 348 121 145 284 210 483 182 504 248 139 495 180 87 28 181 194 457 388 217 432 100 84 405 161 383 373 82 300 95 466 403 490 78 273 410 22 310 86 41 110 435 337 313 479 381 206 386 234 142 267 469 314 389 11 188 407 439 239 256 113 93 172 107 454 378 425 13 18 417 57 35 263 233 205 178 32 377 1 138 465 361 464 442 70 467 494 196 396 207 500 453 397 294 423 43 23 311 193 493 422 191 127 379 96 450 92 404 236 73 75 448 38 367 444 60 99 225 201 108 103 356 124 16 105 230 323 189 216 Test #3: 509 188 356 284 398 369 478 497 227 111 378 46 292 174 460 429 391 455 445 181 418 491 203 309 244 321 215 269 257 415 353 389 258 9 500 60 76 235 288 278 151 361 300 413 506 206 496 7 202 265 82 20 86 366 405 226 323 149 417 31 26 130 466 414 355 437 502 408 448 509 212 103 155 159 486 465 354 193 135 99 454 338 316 160 223 426 508 65 281 144 443 43 217 145 238 157 225 282 488 214 85 79 205 67 308 71 360 83 41 59 196 122 94 40 233 115 126 152 182 275 123 268 490 484 91 190 169 315 254 476 401 505 474 279 17 105 412 63 117 146 475 287 191 440 197 318 247 199 166 363 384 224 33 274 402 291 388 16 89 293 367 189 119 12 14 348 162 245 385 335 372 210 192 446 68 260 379 339 277 392 45 359 319 18 432 393 271 4 487 250 142 324 283 423 60 356 48 371 431 395 70 144 408 127 360 3 92 148 376 160 192 193 454 17 105 212 245 269 316 156 158 96 451 47 293 329 504 9 124 500 101 78 462 149 325 498 88 317 288 287 86 280 8 181 414 244 401 479 81 328 438 80 139 400 407 203 499 123 125 53 445 501 319 214 77 363 471 415 290 367 63 447 173 327 263 350 509 502 506 419 379 16 67 240 478 242 358 219 172 113 230 83 323 2 491 422 274 457 296 426 339 21 297 36 228 41 397 138 143 410 318 130 59 6 369 239 439 145 35 95 151 428 30 102 314 389 466 361 487 432 298 58 201 442 177 188 205 135 157 218 474 147 34 417 271 300 403 392 477 368 276 262 200 117 467 390 141 372 425 388 79 24 427 261 131 347 194 436 334 294 93 25 51 435 223 74 322 222 279 459 362 26 340 383 28 246 394 13 303 224 302 66 38 20 250 196 489 29 110 470 472 140 285 54 62 332 253 198 142 357 27 108 421 333 452 61 57 72 483 49 354 313 115 374 134 295 284 98 345 496 464 234 338 55 184 23 243 146 391 326 497 175 505 182 231 167 488 377 162 43 387 411 321 5 312 373 320 404 199 465 446 399 170 405 440 251 270 210 174 492 463 50 166 337 272 305 342 484 209 155 221 178 310 202 73 444 430 346 132 448 168 236 343 365 260 153 111 336 215 213 461 292 424 476 37 380 495 351 229 335 227 100 1 508 136 165 119 71 315 490 507 344 364 197 386 429 89 103 450 122 248 56 460 126 217 169 453 176 112 76 189 413 133 7 307 179 259 Test #4: 505 459 193 267 328 201 385 380 254 426 392 66 153 22 222 53 250 369 210 306 95 433 387 196 320 318 295 59 112 187 452 220 147 313 269 15 346 341 103 39 444 60 126 260 125 293 116 109 127 62 451 118 384 65 474 294 331 160 111 467 479 495 108 192 132 94 123 449 434 297 229 247 57 180 7 457 505 181 200 271 275 78 72 128 89 31 447 182 79 13 330 199 163 337 82 288 499 477 81 446 169 349 6 462 492 85 56 282 367 234 189 10 359 421 207 114 487 408 5 315 286 47 156 84 342 239 206 326 139 197 211 146 276 365 92 460 464 32 218 155 183 148 334 259 223 348 212 314 417 18 309 494 195 344 33 360 83 14 2 232 167 44 176 193 110 480 403 292 93 454 45 321 235 471 40 266 262 34 243 307 175 8 381 99 50 143 443 419 224 500 356 157 161 240 24 465 152 375 20 214 145 154 482 428 113 412 427 483 280 106 101 377 36 317 504 493 364 435 486 129 221 274 396 27 186 401 354 165 284 63 368 164 228 173 402 382 124 429 135 46 76 80 142 249 355 191 393 373 399 120 17 374 323 216 194 490 372 261 107 400 51 303 394 329 231 217 130 450 322 251 213 391 319 379 205 96 325 91 140 9 456 466 376 43 233 184 453 185 158 203 100 496 88 52 461 177 501 225 468 410 448 350 55 437 188 281 333 459 71 439 174 21 87 204 438 48 431 37 418 102 311 357 264 30 170 277 26 28 481 202 366 11 12 86 1 136 327 230 90 97 29 378 166 131 133 237 470 168 463 248 172 485 411 440 238 491 441 256 227 296 151 478 398 458 255 289 241 68 70 388 144 343 119 424 98 304 423 358 42 362 208 242 179 406 475 409 305 298 35 253 351 301 497 263 138 64 324 49 383 414 415 162 332 404 3 420 300 310 488 425 503 353 345 16 134 219 252 58 336 476 283 340 273 150 436 347 473 4 312 38 370 335 141 469 215 115 361 405 190 236 397 159 104 472 339 73 302 291 122 265 299 268 363 23 407 117 272 442 75 209 445 413 175 103 128 253 323 225 58 83 393 80 65 469 149 487 113 314 275 243 454 166 196 494 478 232 10 322 96 444 51 250 121 136 450 302 394 156 91 112 452 473 415 151 349 146 244 206 21 299 124 390 420 150 257 260 279 303 413 115 273 490 57 298 474 16 158 334 391 370 238 192 79 404 35 365 417 396 353 351 367 200 127 386 416 377 1 213 295 488 500 102 300 221 371 25 467 439 301 345 477 278 412 292 373 171 503 248 201 52 78 168 266 38 372 138 50 263 88 406 251 183 45 271 46 357 162 104 282 125 95 167 306 204 468 328 463 189 407 33 70 207 325 475 77 333 218 230 109 114 130 17 342 217 240 366 276 432 419 482 197 231 317 350 107 449 134 133 285 19 234 363 216 76 40 247 428 99 283 329 3 154 144 66 187 470 262 203 159 101 131 423 108 453 220 Test #5: 507 423 373 364 159 25 192 224 504 486 344 418 83 86 186 400 265 469 229 500 209 321 256 171 32 34 7 443 118 242 156 357 253 394 137 336 239 412 19 426 334 140 36 295 152 13 77 378 12 173 451 467 323 190 56 367 8 247 395 134 46 91 185 420 396 121 30 108 376 434 100 170 246 392 11 342 313 70 444 471 402 484 272 5 148 106 449 478 280 52 409 162 110 201 172 55 404 416 355 487 258 374 84 211 136 435 311 490 142 58 203 481 15 245 42 283 89 14 182 250 275 477 424 314 27 97 459 166 461 79 197 72 181 176 183 158 458 141 343 216 403 433 196 262 501 226 506 237 356 85 291 470 127 312 62 296 18 350 17 308 9 382 21 113 180 115 263 324 390 290 206 20 122 503 4 457 338 317 365 302 492 214 174 393 398 489 227 112 442 53 68 277 168 243 406 309 39 440 101 94 221 341 464 327 441 488 87 143 453 473 454 380 223 310 151 259 236 270 432 24 286 29 202 385 75 33 448 419 41 138 240 502 261 49 164 446 326 150 493 153 35 95 69 6 371 316 59 387 325 16 335 48 193 407 428 386 300 417 425 505 438 319 307 450 102 408 368 466 22 213 370 264 496 257 339 157 215 372 413 65 483 269 293 254 187 178 255 125 479 252 405 465 498 82 149 80 76 130 320 414 351 322 268 480 360 445 147 3 289 26 497 217 38 331 287 456 194 109 485 133 230 119 219 128 244 366 294 383 207 410 267 228 379 177 475 352 160 421 274 422 397 107 167 249 349 43 315 57 71 388 266 179 345 225 31 241 88 2 126 212 51 436 195 415 282 278 348 303 353 50 430 384 104 60 145 78 462 40 66 276 218 439 114 1 155 233 273 460 175 200 67 146 455 238 463 472 297 468 447 96 476 92 169 129 337 199 131 124 482 232 191 306 423 495 354 23 305 208 99 189 37 63 139 304 381 161 213 78 480 327 441 110 12 506 315 402 339 211 232 37 452 1 218 475 58 320 62 139 447 72 67 408 365 371 134 301 40 420 470 499 236 123 117 4 385 209 478 226 372 171 487 346 98 147 433 250 416 308 436 368 18 194 403 108 297 86 173 158 337 282 391 248 243 159 47 16 457 10 43 175 404 247 296 239 428 435 331 384 451 415 160 278 104 172 359 495 183 150 168 90 303 200 453 504 60 485 193 103 212 35 64 284 182 217 498 13 494 326 382 71 377 76 24 204 319 151 205 27 305 113 355 409 36 269 423 266 289 228 152 265 419 353 442 272 246 334 285 311 429 465 344 21 80 114 42 192 477 479 23 437 69 156 378 322 128 286 121 370 146 472 148 460 177 373 454 109 215 181 338 471 358 100 233 259 252 350 397 202 459 219 273 304 342 400 126 493 190 281 295 165 407 144 323 410 483 490 28 210 91 135 357 32 242 264 422 464 444 70 333 129 489 223 497 111 500 361 427 258 379 255 19 290 89 476 354 26 8 145 458 352 88 432 46 351 467 189 25 341 2 197 17 330 450 224 225 398 48 41 261 127 253 143 125 418 39 496 44 321 96 216 336 456 445 275 387 274 240 462 507 140 195 375 187 412 170 53 481 22 310 167 131 363 220 115 14 188 75 482 390 340 325 97 66 81 124 468 138 271 149 280 137 502 132 349 102 179 56 208 15 396 244 118 268 238 38 356 294 426 141 376 345 162 9 61 347 293 389 116 288 51 307 283 245 491 142 474 174 107 198 263 313 324 184 438 492 348 463 235 312 329 257 101 328 30 169 406 55 469 229 130 11 309 164 65 298 276 394 332 136 Test #6: 507 360 390 296 280 369 211 400 7 170 91 440 56 6 292 375 298 308 77 52 40 131 50 238 460 147 157 22 116 463 358 473 37 422 66 160 65 332 471 406 359 420 201 366 155 284 4 436 222 456 161 145 82 465 194 113 104 412 449 43 195 304 478 493 270 41 302 432 269 451 248 428 387 207 181 93 111 495 24 217 210 230 415 174 119 330 233 137 138 62 115 139 3 286 26 246 319 199 356 81 249 496 80 458 421 450 149 480 120 404 352 15 278 433 303 462 252 274 239 129 318 376 128 326 490 414 325 410 124 143 208 100 108 498 437 503 102 148 378 291 34 443 202 67 391 320 154 241 293 27 204 314 383 107 348 95 156 445 439 140 377 232 63 88 413 48 317 393 283 475 355 51 253 390 133 47 295 370 70 164 468 61 73 466 482 263 76 10 153 259 226 363 321 426 257 179 316 165 171 243 87 32 74 461 394 200 185 381 234 30 9 13 419 507 86 78 483 135 186 126 152 8 205 485 464 337 198 368 305 42 279 125 261 146 360 130 469 245 501 75 20 54 290 262 122 182 294 331 267 260 306 487 68 114 127 324 236 425 268 384 31 386 106 367 335 434 297 132 19 398 423 235 282 409 405 11 494 172 229 476 25 168 17 481 183 427 285 192 453 136 79 457 251 21 350 216 178 212 167 435 329 289 97 109 225 58 479 486 206 273 121 191 162 506 310 175 281 35 272 288 227 300 344 346 396 499 374 362 193 256 459 382 36 397 447 64 90 45 275 92 430 438 144 240 341 395 72 351 399 418 99 123 424 57 254 429 250 180 444 474 110 219 500 16 89 207 465 6 326 315 467 432 503 33 359 239 81 346 247 347 231 494 178 396 101 147 69 53 243 397 335 246 106 51 332 286 267 504 406 270 469 159 483 356 269 380 62 312 311 495 149 378 58 466 373 209 82 72 146 194 7 46 232 70 490 496 395 229 112 285 255 1 287 341 103 427 123 367 202 154 160 236 391 145 90 265 3 399 100 124 478 264 158 402 29 128 61 253 165 327 249 459 195 65 45 282 175 215 441 330 369 309 84 211 440 252 283 463 342 398 477 308 142 156 288 122 235 297 176 453 113 50 60 374 205 212 184 214 140 361 132 475 336 131 157 240 137 4 339 497 404 417 196 144 388 256 118 114 225 179 428 289 136 193 334 22 206 121 21 430 498 410 172 390 254 421 319 151 492 479 455 244 414 107 248 433 274 442 139 18 470 302 408 20 409 394 233 468 66 79 462 365 321 349 276 150 47 372 331 223 80 111 75 357 83 325 67 322 32 354 313 271 382 199 251 27 316 507 407 97 15 387 447 210 461 294 125 363 245 162 222 299 259 126 471 10 393 400 102 473 431 148 30 305 76 272 434 19 310 198 170 40 499 301 340 353 220 358 49 130 343 303 39 169 163 153 36 338 13 476 109 44 290 88 485 174 405 200 403 226 25 419 348 324 273 261 292 413 277 486 411 384 480 2 472 191 85 219 204 183 216 115 213 166 484 201 35 448 328 445 500 167 91 56 436 38 482 306 105 379 298 182 371 181 437 228 263 456 177 197 337 42 98 48 360 161 296 59 143 449 439 23 250 333 368 381 307 280 185 392 318 119 208 370 460 425 95 117 314 94 186 92 383 257 412 489 493 52 389 351 426 355 141 87 129 260 237 366 99 14 190 266 502 Test #7: 509 54 90 366 442 288 188 97 211 433 126 413 464 124 379 447 67 200 204 197 274 123 152 216 490 108 506 258 420 223 382 245 403 85 16 71 15 325 439 235 36 347 173 505 194 239 198 399 289 313 419 134 192 127 279 80 70 454 24 189 339 319 499 232 360 59 382 52 254 287 288 463 277 283 434 146 300 190 396 45 134 110 399 256 452 246 248 477 455 468 447 158 290 170 245 265 373 338 30 362 427 289 274 501 271 488 97 411 226 383 347 76 380 335 307 486 125 121 116 279 445 224 286 315 40 377 8 456 241 237 436 318 164 326 393 459 333 366 479 225 439 242 349 497 352 404 138 Test #8: 505 335 220 80 449 382 365 332 63 464 154 72 208 419 204 64 309 1 202 87 416 188 473 237 32 389 478 26 253 353 75 203 209 187 140 141 15 494 408 113 106 31 163 352 268 372 313 440 369 395 472 462 346 238 214 43 400 490 423 499 430 198 255 53 426 485 324 115 189 437 297 130 170 137 150 356 328 190 298 370 250 254 411 158 2 295 211 294 377 471 315 304 279 305 66 503 180 40 425 179 134 502 223 488 103 335 102 361 383 317 321 84 171 123 424 492 290 497 178 350 152 109 299 316 10 52 51 219 236 247 308 280 481 39 406 302 41 307 505 45 303 30 217 14 151 148 98 276 435 431 394 329 165 70 446 79 136 133 161 234 360 355 96 135 420 375 333 28 205 292 504 407 42 126 131 427 118 476 12 6 61 380 11 18 421 405 173 263 67 378 264 139 433 77 57 94 325 122 29 330 272 459 132 454 314 458 99 474 216 339 467 501 447 343 415 105 368 218 47 144 74 414 393 357 386 169 138 498 451 461 258 453 212 142 200 434 7 164 76 391 256 287 69 195 266 48 199 367 21 413 483 82 225 404 55 120 376 496 145 210 362 296 326 480 466 283 25 364 347 475 86 119 88 450 371 222 385 285 445 19 46 176 320 322 374 465 191 319 260 477 8 68 469 111 201 147 288 127 146 282 233 242 95 334 5 341 54 27 417 221 363 37 318 186 60 412 177 429 206 155 59 153 89 349 390 194 337 438 175 9 401 284 311 83 331 183 38 399 466 246 143 205 194 163 351 262 230 478 54 342 259 136 68 327 370 62 188 154 493 112 124 83 376 78 440 476 477 358 182 472 99 140 65 307 336 368 432 405 120 360 190 216 390 119 191 234 374 373 409 300 420 299 172 63 175 72 403 337 323 241 107 208 250 474 105 232 479 473 16 385 113 23 325 244 289 313 209 13 21 310 428 426 81 49 328 395 492 280 462 223 213 475 220 128 122 180 53 15 186 85 357 45 242 366 451 322 302 339 364 87 441 333 306 92 444 352 480 346 184 33 165 88 179 24 167 14 399 227 398 411 421 329 247 91 67 178 449 331 285 248 169 433 40 450 448 69 249 504 8 404 51 375 491 295 29 181 76 334 335 490 438 148 343 378 77 494 59 388 131 245 419 463 284 355 283 416 298 461 287 114 350 109 89 239 164 32 381 256 110 413 406 439 392 158 294 129 231 125 207 121 359 94 273 386 219 464 417 354 445 48 267 61 496 166 203 233 467 427
group 2/Project 2 (1).pdf
Group Assignment 2
Due: Thursday, January 21st at 2PM
You are required to work in groups of two or three students. See the provided group guidelines for how to form your groups on canvas. Each group should only submit one copy of the work to canvas, including the project report as a pdf and the code that implements the algorithms. The report should have all member’s names included. You may use Java, Python, C/C++, Matlab, or R. The submission to Canvas can include multiple files. Acceptable file types include pdf, zip, gzip. So you should zip up your code for submission. It is also required that the report is submitted as a separate pdf file so that the TA can directly comment on it via canvas.
Problem Description
The locker room of OSU’s Dixon Recreation Center has N lockers that are labeled 1, 2, . . . , N . Each locker is locked, but be opened using its unique key. Copies of the key to each locker are in its adjacent lockers; i.e. a copy of the key to locker i is placed in locker i+ 1 and i− 1 (the key to locker 1 is only in locker 2 and the key to locker N is only in locker N − 1).
T tennis balls are inside T distinct lockers (and you know which of the lockers they are in). You are given keys to M of the lockers and your goal is to collect all of the tennis balls by opening the least number of lockers. And example input and solution is given below.
Figure 1: In one solution (blue), only the first and last key are used and to collect all of the tennis balls, lockers 1,2,3,4,5,6 and 8,9 are opened. This solution is not optimal. In an optimal solution (red), only the second and third key are used: the second key is used to open locker 3 which gives us access to the keys to locker 2 and 4. In this way, the optimal solution only opens lockers 2,3,4,5,6 and 8,9.
1
You will design, analyze and implement 2 (or 3) algorithms to solve instances of this problem correctly. You may use any language you choose to implement your algorithms. Be sure that your algorithm correctly finds the minimum number of lockers that can be opened to collect all of the tennis balls.
Testing for correctness Above all else, your algorithms should be correct. To aid in testing, a file named dp.txt containing test sets is provided on canvas. The file has 8 test cases. Each test case starts with three integers N (1 ≤ N ≤ 600), M (1 ≤ M ≤ N), T (1 ≤ T ≤ N) that are separated by space where N is the number of lockers, M is the number of initially given keys and T is the number of tennis balls. The next line contains M numbers which represents the labels of the lockers whose keys you are given. The next line contains T numbers that are the labels of lockers that contain tennis balls. For each of these test cases, the minimum number of lockers that you can open to get all the tennis balls is also given. Sample input/output for the example in figure 1 is shown below:
Sample Input Sample Output 9 3 4 1 3 8 2 5 6 9
7
You may use this test file to check that your code is correct. You should also test your code on other small hand-generated instances.
Instructions
Your three algorithms are to be based on the following ideas and should have the given upper bounds on their running times. Note that Algorithm 3 is for extra credit only. You can earn full credit without attempting Algorithm 3. For each algorithm, your report must include:
• pseudocode with sufficient explanation that we can understand your pseudocode
• an analysis (and explanation) of the running time – include lower bounds (Ω) on the running times as well
• solutions to the corresponding input instances
Algorithm 1: Enumeration (Brute-force algorithm) O(N2M ) Hint: Guess which of the keys you are initially given you should use and then can determine (in O(N) time) how best to use them. How many guesses do you need to make? The input instances for this algorithm are stored in dp set1.txt, available on canvas under Group assignment 2.
Algorithm 2: Dynamic Programming O(NM2) Hint: Let d[i] be the minimum number of lockers that must be opened to gather all the tennis balls between the first locker and the locker that key i opens assuming that key i is used. Start your development of a dynamic programming algorithm by figuring out how to compute d[i] recursively and then compute d[i] bottom up. Once you have computed d[i] for all the keys you can choose from, how do you determine the final solution? The input instances for this algorithm are stored in dp set2.txt, available on canvas under Group assignment 2.
Algorithm 3 (Extra Credit): Optimal Dynamic Programming O(T 2 + M) Hint: Can you efficiently decide whether there exist at least one tennis ball between ith and jth locker? (No questions will be answered for this algorithm, since it is extra credit.) The input instances for this algorithm are stored in dp set3.txt, available on canvas under Group assignment 2.
2
