Algorithm to find a group seating arrangement for an open book test -

-

you planning group seating arrangement open book test given list of students, v different schools participate. assuming fact students known each other directly or indirectly cheat more compared unknown people sitting together. suppose given lookup table t t[u] u ? v list of students u knows. if u knows v, v knows u. required arrange seating such student @ table doesn't knows other student sitting @ same table either directly or through other student sitting @ same table. example, if x knows y, , y knows z, x, y, z can sit @ same table. describe efficient algorithm that, given v , t, returns minimum number of tables needed achieve requirement. analyze running time of algorithm.

follow student relations out 2 edges, graph:

a - e - j       \ q  b - d   \ t  r - w - x - y - z

all students in same subgraph have separated, minimum number of tables 1 each students in largest group - in example largest subgraph r-w-x-y-z, 5 tables.

untested python pseudocode:

# given student list # b c d e f j q r t w x y z  # start chain @ # b c d e f j q r t w x y z # .  # visit friends of # b c d e f j q r t w x y z # .       .  # visit friends of a's friends # b c d e f j q r t w x y z # .       .   . .  # if e , j friends, don't double-count  # count of 4 starting @ person # repeat students # report longest chain.  friendcounts = {}  def countfriendsof(t, student, friendtracker, moresteps=2):     friendtracker[student] = true #quicker set regardless,                                   #than check if it's set     if not moresteps:         return      friend in t[student]:         countfriendsof(t, friend, friendtracker, moresteps - 1)      return friendtracker   u in v:     friends = countfriendsof(t, u, friendtracker={})     friendcounts[u] = (len(friends), friends)  results = sorted(friendcounts.items(), key=lambda x: x[1][0], reverse=true) (student, (friendcount, friends)) = results[0]  print "the smallest number of tables is:", friendcount print "mandated friend group of:", student print  pprint import pprint pprint(friends)

analyze running time of algorithm.

analysis: fine on computer more powerful snowglobe.

not sure. best case: students have no friends - linear respect number of students. o(n). worst case: every student friends every other student, lookups every student every student, o(n^3). ew.

it running more o(n^2) until realised version wrong.

this version not-definitely-wrong, isn't definitely-right.

i didn't start recursive solution, ended going way. friendtracker use nasty side-effect, , recursive call not tail recursion optimizable. not python that,


Comments

Post a Comment

Popular posts from this blog

Java 3D LWJGL collision -

-
i making 3d java game lwjgl library, , wondering how add collision detection, player not go through models. i using obj models. here objloader class, loads models: package renderengine; import java.io.bufferedreader; import java.io.file; import java.io.filenotfoundexception; import java.io.filereader; import java.util.arraylist; import java.util.list; import models.rawmodel; import org.lwjgl.util.vector.vector2f; import org.lwjgl.util.vector.vector3f; public class objloader { public static rawmodel loadobjmodel(string filename, loader loader){ filereader fr = null; try { fr = new filereader(new file("res/"+filename+".obj")); } catch (filenotfoundexception e) { system.err.println("couldn't load file!"); e.printstacktrace(); } bufferedreader reader = new bufferedreader(fr); string line; list<vector3f> vertices = new arraylist<vector3f...
Read more

spring - SubProtocolWebSocketHandler - No handlers -

-
i have ugly error during deploying spring app on jboss. 18:11:16,025 error [org.apache.catalina.core.containerbase.[jboss.web].[default-host].[/consumer]] (msc service thread 1-7) exception sending context initialized event listener instance of class org.springframework.web.context.contextloaderlistener: org.springframework.context.applicationcontextexception: failed start bean 'subprotocolwebsockethandler'; nested exception java.lang.illegalargumentexception: no handlers @ org.springframework.context.support.defaultlifecycleprocessor.dostart(defaultlifecycleprocessor.java:176) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.springframework.context.support.defaultlifecycleprocessor.access$200(defaultlifecycleprocessor.java:51) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.springframework.context.support.defaultlifecycleprocessor$lifecyclegroup.start(defaultlifecycleprocessor.java:346) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.s...
Read more

methods - python can't use function in submodule -

-
my folder structure this: pythonstuff/ program.py modulea/ __init__.py foo.py bar.py here's code bar.py : def hello(): print("hello, world!") here's code program.py : #!/usr/bin/env python3 modulea import bar bar.hello() i run $ python3 program.py somehow error: file "program.py", line 3, in <module> bar.hello() attributeerror: 'module' object has no attribute 'hello' edit: __init__.py file empty. edit2: after trying realized had bar.py in root directory contained hello() method. bar.py in modulea/ directory empty. add it import os __all__ = [] module in os.listdir(os.path.dirname(__file__)): if module != '__init__.py' , module[-3:] == '.py': __all__.append(module[:-3]) the init .py files required make python treat directories containing packages; done prevent directories common name, such string, unintentionally hiding v...
Read more